题解 P1585 【魔法阵】

· · 题解

我觉得这题应该蓝。。。

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

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

当然，加上了最显而易见的剪枝：如果当前答案已大于搜索已经得到的最小值，直接 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;
}

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