c/c++语言开发共享洛谷P1585 魔法阵

题目传送门

这题就是一个有技巧的dfs+一大堆乱七八糟的剪枝

进行dfs时注意一下以下点

• 根据题意，我们可以把dfs分成两块，即1--n*m/2与n*m/2--n*m,第一块边找边记录，第二块就开始计算

• 其实左上角与右上角开始没有任何区别

剪枝

1. 可行性剪枝:判断上下与左右走过没有

（画风丑，勿喷）如图所示，当上下两格都走过或左右两个都走过时， 无论怎么走也是遍历完整张图的（自己去画画看就知道了）

1. 最优性剪枝:判断当前最大值是否大于答案

这样下来就行了

看代码:

#include<bits/stdc++.h> using namespace std; int t,n,m,k1,k2,ans=0x3f3f3f3f; int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};//四个方向 int num[60][2];//用于第一次记录，下面会提 bool vis[60][60];//标记走过没 inline void dfs(int x,int y,int sum,int maxn)//x表示当前x坐标，y表示当前y坐标，sum表示当前步数，maxn表示当前最大值 {     //cout<<x<<" "<<y<<" "<<sum<<" "<<maxn<<endl;     if(vis[x-1][y]&&vis[x+1][y]&&!vis[x][y+1]&&!vis[x][y-1])return;//可行性剪枝1     if(vis[x][y-1]&&vis[x][y+1]&&!vis[x+1][y]&&!vis[x-1][y])return;//可行性剪枝2     if(sum<=t)num[sum][0]=x,num[sum][1]=y;//记录，这里t指一半     else     {         maxn=max(maxn,k1*abs(num[sum-t][0]-x)+k2*abs(num[sum-t][1]-y));//进行计算并更新         //return;     }     if(sum>=n*m)     {         ans=min(ans,maxn);//如果遍历完，那么更新答案         return;     }     if(maxn>=ans)return;//最优性剪枝     /*for(int i=0;i<=n+1;i++)     {         for(int j=0;j<=m+1;j++)cout<<vis[i][j];         cout<<endl;     }*/          for(int i=1;i<=4;i++)//四个方向枚举     {         int a=x+dx[i],b=y+dy[i];         if(!vis[a][b])         {                vis[a][b]=1;             //cout<<sum<<endl;             dfs(a,b,sum+1,maxn);             //cout<<sum<<endl;             vis[a][b]=0;//回溯         }     }      } int main() {     cin>>n>>m>>k1>>k2;     t=n*m/2;     for(int i=0;i<=m+1;i++)     {         vis[0][i]=1;         vis[n+1][i]=1;     }//在外围加个边框1     for(int i=0;i<=n+1;i++)     {         vis[i][0]=1;         vis[i][m+1]=1;     }//在外围加个边框2     vis[1][1]=1;//初始标记     /*num[1][0]=1;     num[1][0]=1;     /*for(int i=0;i<=n+1;i++)     {         for(int j=0;j<=m+1;j++)cout<<vis[i][j];         cout<<endl;     }*/     dfs(1,1,1,0);     cout<<ans<<endl;     return 0; }