本文共 1385 字，大约阅读时间需要 4 分钟。
这是道深搜的题目，不过需要回溯。
很早就看了，所以没出啥问题。
“Slyar:说一下题目大意。给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。
"马的遍历"是一道经典回溯题，当然还是DFS...这题有3个要密切注意的地方：
1、题目要求以"lexicographically"方式输出，也就是字典序...一开始没看懂这个词结果WA了N次...要以字典序输出路径，那么方向数组就要以特殊的顺序排列了...这样只要每次从dfs(1,1)开始搜索，第一个成功遍历的路径一定是以字典序排列...
2、国际象棋的棋盘，横行为字母，表示横行坐标的是y；纵行为数字，表示纵行的坐标是x...一开始又搞反了...
3、虽然题目没说，但是这道题最后一组数据后是没有空行的...否则会PE...
其他内容注释里很清楚了...优化了代码，0MS...”
#includeusing namespace std;const int numdirect = 8;int xstep[8] = {-2, -2, -1, -1, 1, 1, 2, 2};int ystep[8] = {-1, 1, -2, 2, -2, 2, -1, 1};const int maxsize = 26;bool visited[maxsize][maxsize];int route[maxsize * maxsize][2];int cnt;int p, q;bool isinmap(int x, int y){ return x >= 0 && x < p && y >=0 && y < q;}void dfs(int x, int y, bool &flag){ visited[x][y] = true; route[cnt][0] = x; route[cnt][1] = y; cnt++; if(cnt == p * q) { flag = true; return; } int nx, ny; for(int i = 0; i < numdirect; ++i) { nx = x + xstep[i]; ny = y + ystep[i]; if(isinmap(nx, ny) && !visited[nx][ny]) { //visited[nx][ny] = true; //route[cnt][0] = i; //route[cnt][1] = j; //cnt++; dfs(nx, ny, flag); if(flag) return; //cnt--; //visited[nx][ny] = false; } } cnt--; visited[x][y] = false;}int main(){ int n; cin>>n; for(int i = 0; i < n; ++i) { cnt = 0; memset(visited, false, maxsize * maxsize); //cnt = 0; cin>>q>>p; bool flag = false; dfs(0, 0, flag); cout<<"Scenario #"<
转载地址：http://ixxli.baihongyu.com/