本题确实没什么好办法,只能暴力搜索,不过要加枚举剪枝和展望剪枝。枚举优化,就是事先试一下所有可行移动位置,搜索是只用这几个就行。
展望及当前已经移动数加上剩下的最低估计也比当前最优解大,剪枝。
还有本解不是最优的,看到有高手用位运算来模拟该搜索过程比纯属组快四倍。
还有用位运算模拟,往前添加尝试不好办啊,若一直往前走数大的存不下,可以将当前的图往后移动,在前面添加。
#include <set> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 10000; int maze[5][maxn]; int x[maxn],y[maxn],n; char str[maxn]; vector<int> ans; void get(){ for(int d=1;d<n;d++){ int ok=1; for(int i=0;i<n;i++){ if(maze[x[i]][y[i]+d]){ ok=0; break; } } if(ok){ ans.push_back(d); } } } int res; void dfs(int D,int step){ if((9-step)*ans[0]+D>=res) return ; if(step==9){ res = D; return ; } for(int i=0;i<ans.size();i++){ int ok=1; for(int j=0;j<n;j++){ if(maze[x[j]][y[j]+ans[i]+D]){ ok=0; break; } } if(ok){ for(int j=0;j<n;j++) maze[x[j]][y[j]+ans[i]+D]=1; dfs(D+ans[i],step+1); for(int j=0;j<n;j++) maze[x[j]][y[j]+ans[i]+D]=0; } } } int main() { while(scanf("%d",&n)==1&&n){ int cnt=0; ans.clear(); memset(maze,0,sizeof(maze)); for(int i=0;i<5;i++){ scanf("%s",str); for(int j=0;j<n;j++){ if(str[j]=='X'){ x[cnt]=i; y[cnt++]=j; maze[i][j] = 1; } } } get(); res = 9*n; dfs(0,0); printf("%d\n",res+n); } return 0; }