自动搬运

查看原文

来自洛谷，原作者为

	YellowBean_Elsa You find me waiting in the wings......

搬运于2025-08-24 21:26:46，当前版本为作者最后更新于2020-02-16 12:01:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我觉得这题应该蓝。。。

首先看数据范围可知，这题就是个普通搜索。

然后按照题意，很快写出了一个简单的暴搜。

当然，加上了最显而易见的剪枝：如果当前答案已大于搜索已经得到的最小值，直接 return;

然而这样T飞了。。。

然后我们注意到，题目还有一个限制条件：每个格子必须且仅能经过一次

那么，如果在某一个状态时，我们可以判断此时已经不可能按要求走完魔法阵，则可以直接 return;

knock the blackboard!!!

经过画图，我们找到了一种这样的状态：

当我们走到一个位置时,如果已经走过它的上下，却没有走过它左右的任意一格，或者相反，已经走过它的左右，却没有走过它上下的任意一格，那么一定无法走完魔法阵，直接 return;

证明：如图，从A走到B的路径隔绝了C和D，因此不可能在不经过A到B路径的情况下同时走到C和D，证毕。

加上这个可行性剪枝后，就AC了。

//coder: Feliks-GMYB
#include<bits/stdc++.h>
using namespace std;
int n,m,k1,k2,ans=(1<<30);
bool vis[55][55];
int col[30][2];
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x;
}void dfs(int x,int y,int p,int mx){
	//可行性剪枝
	if(vis[x-1][y]&&vis[x+1][y]&&!vis[x][y+1]&&!vis[x][y-1])return;
	if(!vis[x-1][y]&&!vis[x+1][y]&&vis[x][y+1]&&vis[x][y-1])return;
	if(mx>ans)return;//显而易见的最优性剪枝
	//按照公式要求进行操作
	if(p<=((n*m)>>1)){
		col[p][0]=x;
		col[p][1]=y;
	}else mx=max(mx,abs(col[p-n*m/2][0]-x)*k1+abs(col[p-n*m/2][1]-y)*k2);
	if(p==n*m){//done the maze
		if(mx<ans)ans=mx;
		return;
	}//尝试向四面走 
	if(!vis[x-1][y]){
		vis[x-1][y]=1;
		dfs(x-1,y,p+1,mx);
		vis[x-1][y]=0;
	}//up
	if(!vis[x+1][y]){
		vis[x+1][y]=1;
		dfs(x+1,y,p+1,mx);
		vis[x+1][y]=0;
	}//down
	if(!vis[x][y-1]){
		vis[x][y-1]=1;
		dfs(x,y-1,p+1,mx);
		vis[x][y-1]=0;
	}//left
	if(!vis[x][y+1]){
		vis[x][y+1]=1;
		dfs(x,y+1,p+1,mx);
		vis[x][y+1]=0;
	}//right
}int main(){
	n=read(),m=read(),k1=read(),k2=read();
	//常见搜索防越界操作：
	//地图四周初始时赋为已走过，防止搜索时走出地图 
	for(int i=0;i<=n+1;i++)
		vis[i][0]=vis[i][m+1]=1;
	for(int i=0;i<=m+1;i++)
		vis[0][i]=vis[n+1][i]=1;
	vis[1][1]=1;dfs(1,1,1,0);
	printf("%d\n",ans);
    return 0;
}

多嘴一句，这种可行性剪枝对于所有要求一笔画方格图的搜索都适用，也可看作一种实用技巧