POJ 2488 A Knight's Journey (dfs+改变搜索顺序）

题目链接

POJ 2488

题目大意

给定一个n*m的棋盘，一个跳“日”字的马可以从任一个格子开始去遍历棋盘，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。 棋盘的编号：n（行）方向由递增的数字编号，m（列）方向按递增的字母编号。

分析

本题是经典的“骑士游历问题”，搜索的入门题。基本思路即枚举起点进行dfs,并记录路径。要注意的是题目要求输出的路径字典需最小，应注意搜索顺序： 1.枚举起点时要先枚举列，再枚举行来保证字典序从小到大枚举。 2.每一位置向下一个位置搜索时，要按如下图的顺序： 这对方向数组的顺序提出了要求。 这道题我做的时候一开始WA了，因为只考虑了枚举起点的顺序，方向数组的顺序错误了。

代码

#include <iostream> #include <cstring> #include <string> #include <cstdio> using namespace std; int vis[28][28],n,m; string step[1000]; bool flag; bool can(int x,int y) { if (1<=x&&x<=n&&1<=y&&y<=m&&!vis[x][y]) return true; return false; } void dfs(int x,int y,int sum) { int d[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}}; //方向数组顺序不能错 if (flag) return; vis[x][y]=1; step[sum]+=('A'+y-1); step[sum]+=('0'+x); if (sum==n*m) { flag=true; return; } for (int i=0;i<=7;i++) { int xx=x+d[i][0]; int yy=y+d[i][1]; if (can(xx,yy)) dfs(xx,yy,sum+1); } if (flag) return; vis[x][y]=0; step[sum]=""; } void Init() { memset(vis,0,sizeof(vis)); flag=false; for (int i=1;i<=n*m;i++) step[i]=""; } int main() { int t,i,j,cnt=0; cin>>t; while (t--) { cout<<"Scenario #"<<++cnt<<":"<<endl; cin>>n>>m; Init(); for (j=1;j<=m;j++) //先枚举列，再枚举行 for (i=1;i<=n;i++) if (!vis[i][j]) dfs(i,j,1); if (flag) { for (i=1;i<=n*m;i++) cout<<step[i]; printf("\n"); } else cout<<"impossible"<<endl; if (t!=0) printf("\n"); } return 0; }