#1308 : 搜索二·骑士问题
描述
小Hi：小Ho你会下国际象棋么？
小Ho：应该算会吧，我知道每个棋子的移动方式，马走日象飞田什么的...
小Hi：象飞田那是中国象棋啦！
小Ho：哦，对。国际象棋好像是走斜线来着。
小Hi：不过马走日倒是对了。国际象棋中的马一般叫做骑士，关于它有个很有意思的问题。
小Ho：什么啊？
小Hi：骑士巡游问题，简单来说就是关于在棋盘上放置若干个骑士，然后探究移动这些骑士是否能满足一定的而要求。举个例子啊：一个骑士从起始点开始，能否经过棋盘上所有的格子再回到起点。
小Ho：哦，看上去好像很难的样子。
小Hi：其实也还好了。简单一点的比如棋盘上有3个骑士，能否通过若干次移动走到一起。
小Ho：能够么？
小Hi：当然能够了。由于骑士特殊的移动方式，放置在任何一个初始位置的骑士，都可以通过若干次移动到达棋盘上任意一个位置。
小Ho：那么只要选定一个位置，把它们全部移动过去就好了是吧？
小Hi：是的，那么这里又有另一个问题了：要选择哪一个位置汇合，使得3个骑士行动的总次数最少？
小Ho：嗯，这个好像不是很难，让我想一想。
输入
第1行：1个正整数t，表示数据组数，2≤t≤10。
第2..t+1行：用空格隔开的3个坐标, 每个坐标由2个字符AB组成，A为'A'~'H'的大写字母，B为'1'~'8'的数字，表示3个棋子的初始位置。
输出
第1..t行：每行1个数字，第i行表示第i组数据中3个棋子移动到同一格的最小行动步数。
- 样例输入
-
2 A1 A1 A1 B2 D3 F4
- 样例输出
-
0 2
思路：
利用队列做bfs，求出当前位置到棋盘上所有位置的最短距离，然后，三个棋子到棋盘位置的最短距离和
AC代码：
1 #include "iostream" 2 #include "string.h" 3 #include "queue" 4 5 using namespace std; 6 7 typedef pair<int, int> pii; 8 char ss[3]; 9 int vis[3][8][8]; 10 int d[8][2] = { { -2,1 },{ -2,-1 },{ -1,-2 },{ -1,2 },{ 2,-1 },{ 2,1 },{ 1,-2 },{ 1,2 } }; 11 int step = 0; 12 13 pii pos; //马位置 14 15 bool in(pii p) 16 { 17 if (p.first < 0 || p.second < 0 || p.first>7 || p.second>7) 18 return false; 19 else 20 return true; 21 } 22 23 void bfs(int vi[8][8]) 24 { 25 step = 0; 26 queue<pii> q; 27 memset(vi, -1, 256); 28 q.push(pos); 29 vi[pos.first][pos.second] = 0; 30 31 while (!q.empty()) 32 { 33 pii pfront = q.front(); 34 q.pop(); 35 for (int i = 0; i < 8; i++) 36 { 37 pii temp; 38 temp.first = pfront.first + d[i][0]; 39 temp.second = pfront.second + d[i][1]; 40 if (in(temp) && vi[temp.first][temp.second] == -1) 41 { 42 vi[temp.first][temp.second] = vi[pfront.first][pfront.second] + 1; 43 q.push(temp); 44 } 45 } 46 } 47 } 48 49 int main() 50 { 51 int t; 52 cin >> t; 53 while (t--) 54 { 55 scanf("%s", ss); 56 pos = make_pair(ss[0] - 'A', ss[1] - '1'); 57 bfs(vis[0]); 58 59 scanf("%s", ss); 60 pos = make_pair(ss[0] - 'A', ss[1] - '1'); 61 bfs(vis[1]); 62 63 scanf("%s", ss); 64 pos = make_pair(ss[0] - 'A', ss[1] - '1'); 65 bfs(vis[2]); 66 67 int ans = 1e9; 68 for (int i = 0; i < 8; i++) 69 { 70 for (int j = 0; j < 8; j++) 71 { 72 int temp = 0; 73 for (int k = 0; k < 3; k++) 74 { 75 temp += vis[k][i][j]; 76 } 77 if (temp < ans) 78 ans = temp; 79 } 80 } 81 cout << ans << endl; 82 } 83 }
补充：
提供另一种思路，因为是8x8的棋盘，可以模拟成8进制的一个数，这样3个旗子就是一个6位的8进制数。
由此可以通过一个大小为8^6的布尔数组来进行状态的判重。而每一次的状态转移也从原来的仅枚举8个方向，变成了枚举骑士加枚举方向，一共有3*8=24种可能。
此方法的伪代码为：
queue.push( initialStatus ) // 将初始的8进制数加入队列中 while (!queue.isEmpty()) now_status = queue.pop() // 弹出队列头元素 For i = 1 .. 3 // 枚举移动的其实 For j = 1 .. 8 // 枚举8种可能的移动 next_status = move(now_status, i, j) // 移动骑士并记录状态 If (next_status is valid AND not visited[ next_status ]) step[ next_status ] = step[ now_status ] + 1 queue.push( next_status ) If (check(next_status)) Then // 检查这个八进制数是否满足3个坐标重合 Return step[ next_status ] End If End If End For End While
在进行检查是否已经走到一起时，可以通过一个位运算来做：
check(status): Return ((status and 0x3f) == ((status rsh 6) and 0x3f)) and (((status rsh 6) and 0x3f) == ((status rsh 12) and 0x3f)) // rsh表示右移操作
小Ho：哦，这样就可以不用计算出每个骑士走到每个点的步数，而是在过程中就有可能直接求解到最先汇合位置的步数。
小Hi：对，不过这个算法中状态的转移会稍微复杂一点。你可以选择一个你比较喜欢的方法来实现。
小Ho：好！