POJ2488 骑士的旅程
题目描述
骑士一次又一次地看到相同的黑白方块而感到厌倦，并决定环游世界。每当骑士移动时，它是一个方向上的两个正方形和一个垂直于此的正方形。骑士的世界是他生活的棋盘。我们的骑士生活在棋盘上，棋盘面积比普通的8 * 8棋盘小，但它仍然是长方形的。你能帮助这个冒险骑士做出旅行计划吗
输入
找到一条路径，使骑士可以拜访每个广场一次。骑士可以在棋盘的任何正方形上开始和结束。
输出
输入在第一行中以正整数n开头。以下各行包含n个测试用例。每个测试用例由一行包含两个正整数p和q的行组成，因此1 <= p * q <=26。这表示 p * q棋盘，其中p描述了多少个不同的正方形数1,2,3…，q描述存在多少个不同的正方形字母,这些是拉丁字母的前q个字母：A ,B,C…
输入样例
3
1 1
2 3
4 3
输出样例
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
思路分析
本题主要考察DFS.但要明白这个题的意思是能否只走一遍(不回头)将这个地图走完,这与普通的DFS不同,普通的DFS是一直走,走不通后返回某处继续进行搜索.所以这个题还要用到回溯思想,如果不重复走一遍走完了就做一个标记,算法就结束.否则在某种DFS下走到某一步时按照马跳的规则无路可走但地图还没有走完时,就撤销这一步,切换其他路线.撤销这一步后应该重置该点,以便走其他路线时该点是未访问过的,而不是像普通的DFS当做已经访问过了.
如果有多种方式可以不重复走一遍的走完，需要输出按字典序最小的路径，而注意到国际象棋的棋盘是列为字母，行为数字，如果能够不回头走一遍的走完，一定会经过A1点，所以我们应该从A1开始搜索，以确保之后得到的路径字典序是最小的（也就是说如果路径不以A1开始，该路径一定不是字典序最小路径），而且我们应该确保优先选择的方向是字典序最小的方向，这样我们最先得到的路径就是字典序最小的。
算法设计
2.图是p行q列的，行用数字标识，列用大写字母标识，但是输出时，
先输出了大写字母，然后是数字，因此写程序时，把图翻转一下，看作q行p列的，这样就可以先行后列输出了(所以上图坐标也进行了反转)。
3. 从1，1开始，从八个方向深度优先搜索，判断是否可行，如果可行，记录搜索步，从当前结点出发继续深搜;
4. 当步数达到n*m说明找到一条路径。。
5.输出该路径。
参考代码
#include<iostream> #include<string.h> using namespace std; int map[30][30],m,n;//m:行, n:列 map:标记是否走过. bool flag;//控制是否完成旅行. int path[30][2];//记录路径 int dir[8][2] = { -2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1 };//-2,-1,-1,-2,1,-2,2,-1,2,1,1,2,-1,2,-2,1 bool dfs(int x, int y, int step) { if (step == m * n) return flag = true; for (int i = 0; i < 8; i++) { int x2 = x + dir[i][0]; int y2 = y + dir[i][1]; if (x2 >= 1 && x2 <= m && y2 >= 1 && y2 <= n && !map[x2][y2] && !flag) { map[x2][y2] = 1; path[step][0] = x2; path[step][1] = y2; dfs(x2, y2, step+1); map[x2][y2] = 0;//如果该路不通,则回溯. } } return flag; } int main() { int T = 0; cin >> T; for(int i = 1; i <= T; i++) { memset(map, 0, sizeof(map)); flag = false; cin >> n >> m; int step = 1; path[0][0] = 1; path[0][1] = 1; map[1][1] = 1; cout << "Scenario #" << i<<":"<<endl; if (dfs(1, 1, 1))//如果有路 { for (int j = 0; j < m * n; j++) { cout << (char)(path[j][0]+'A' - 1) << path[j][1]; } cout << endl; } else { cout << "impossible" << endl; } cout << endl; } return 0; }
