题目传送门
这题就是一个有技巧的dfs+一大堆乱七八糟的剪枝
进行dfs时注意一下以下点
-
根据题意,我们可以把dfs分成两块,即
1--n*m/2
与n*m/2--n*m
,第一块边找边记录,第二块就开始计算 -
其实左上角与右上角开始没有任何区别
剪枝
- 可行性剪枝:判断上下与左右走过没有
(画风丑,勿喷)如图所示,当上下两格都走过或左右两个都走过时, 无论怎么走也是遍历完整张图的(自己去画画看就知道了)
- 最优性剪枝:判断当前最大值是否大于答案
这样下来就行了
看代码:
#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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605853.html