博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P1585 魔法阵
阅读量:4550 次
发布时间:2019-06-08

本文共 2328 字,大约阅读时间需要 7 分钟。

#include 
#define ll long long#define INF 2147483647#define mem_INF 2139062143#define ll_INF 9223372036854775807#define eps 1e-8#define fuckrand() ( ( rand() << 15 ) ^ rand() )using namespace std;inline int read() { int x = 0,tmp = 1;char ch = getchar(); while( ch < '0' || ch > '9' ) {if ( ch == '-' ) tmp = -1; ch = getchar();} while( ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar(); } return x * tmp;}bool _map[51][51];int N, M, k1, k2, p[2600][2], ans = INF;bool dir_1( int x, int y ) { return !( x + 1 > N || _map[x + 1][y] );}bool dir_2( int x, int y ) { return !( y + 1 > M || _map[x][y + 1] );}bool dir_3( int x, int y ) { return !( x - 1 < 1 || _map[x - 1][y] );}bool dir_4( int x, int y ) { return !( y - 1 < 1 || _map[x][y - 1] );}inline void dfs_2( int x, int y, int now, int sum ) { if( sum > ans ) return; if( now >= ( N * M ) >> 1 ) { sum = max( k1 * abs( x - p[now][0] ) + k2 * abs( y - p[now][1] ), sum ); ans = min( ans, sum ); return; } if( ( ( dir_2( x, y ) && dir_4( x, y ) ) && !( dir_1( x, y ) || dir_3( x, y ) ) ) || ( !( dir_2( x, y ) || dir_4( x, y ) ) && ( dir_1( x, y ) && dir_3( x, y ) ) ) ) return; _map[x][y] = 1; sum = max( k1 * abs( x - p[now][0] ) + k2 * abs( y - p[now][1] ), sum ); if( dir_1( x, y ) ) dfs_2( x + 1, y, now + 1, sum ); if( dir_2( x, y ) ) dfs_2( x, y + 1, now + 1, sum ); if( dir_3( x, y ) ) dfs_2( x - 1, y, now + 1, sum ); if( dir_4( x, y ) ) dfs_2( x, y - 1, now + 1, sum ); _map[x][y] = 0;}inline void dfs_1( int x, int y, int now ) { if( now > ( M * N ) >> 1 ) { dfs_2( x, y, 1, 0 ); return; } if( ( ( dir_2( x, y ) && dir_4( x, y ) ) && !( dir_1( x, y ) || dir_3( x, y ) ) ) || ( !( dir_2( x, y ) || dir_4( x, y ) ) && ( dir_1( x, y ) && dir_3( x, y ) ) ) ) return; _map[x][y] = 1; p[now][0] = x; p[now][1] = y; if( dir_1( x, y ) ) dfs_1( x + 1, y, now + 1 ); if( dir_2( x, y ) ) dfs_1( x, y + 1, now + 1 ); if( dir_3( x, y ) ) dfs_1( x - 1, y, now + 1 ); if( dir_4( x, y ) ) dfs_1( x, y - 1, now + 1 ); _map[x][y] = 0;}int main() { N = read(), M = read(), k1 = read(), k2 = read(); dfs_1( 1, M, 1 ); printf( "%d\n", ans ); return 0;}

转载于:https://www.cnblogs.com/ARZhu-NOIpAK/p/6675253.html

你可能感兴趣的文章
图像处理的软件
查看>>
Sql 2000系统表 语句查询表结构
查看>>
[CentOS_7.4]Linux编译安装ffmpeg
查看>>
大数据存储平台之异构存储实践深度解读
查看>>
1.2 Stream API
查看>>
Less2css error 终极解决方案
查看>>
DNS服务器的原理
查看>>
django_数据库操作—增、删、改、查
查看>>
django_mysql_配置
查看>>
day 37 并发编程和操作系统的发展史 + 进程
查看>>
面试问题总结
查看>>
python 15 days
查看>>
悟透JavaScript (强烈推荐)
查看>>
让我们再聊聊浏览器资源加载优化
查看>>
underscore demo
查看>>
CSS hack
查看>>
C# Enum Name String Description之间的相互转换
查看>>
Android 实现ripple动画
查看>>
PHP wamp server问题
查看>>
Spring Data Redis学习
查看>>