题目链接:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380
知识点:
bfs
dfs
查阅资料汇总:
http://blog.csdn.net/ns_code/article/details/19617187
http://www.cnblogs.com/whywhy/p/4888632.html
http://blog.csdn.net/dreamzuora/article/details/51137132
http://blog.csdn.net/u011437229/article/details/53188837
http://www.cnblogs.com/gczr/p/6476577.html
https://zhidao.baidu.com/question/2011995849177182268.html
*/
/* 法一: 参考了: http://www.cnblogs.com/xien0/archive/2013/08/08/Knigth-Moves.html 法一没有用STL,它的思路要点在于: 用数组来模拟队列 这个思路我在之前做Java实验时也用过,链接见下: http://blog.csdn.net/mofushaohua_ln/article/details/78164383 之所以自己重敲这个方法,还因为这个方法有点特别,一般我们是要会把棋盘设置为二维数组的, */ #include <cstdio> #include <cstring> #define rep(i, n) for (int i = 0; i < (n); i++) int drc[8][2] = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, -1 }, { 2, 1 }, { -2, 1 }, { -2, -1 } }; //drc为骑士移动方向的坐标变化量, r::row, c:: column int que[100], vis[10][10], ans[10][10]; void bfs(int r, int c) { int tail = 1, head = 0; //队列的头和尾 que[head] = r * 8 + c; vis[r][c] = 1; while (tail > head) { int now = que[head++]; //取列表的首元素 r = now / 8, c = now % 8; vis[r][c] = 1; rep(i, 8) { int r1 = r + drc[i][0], c1 = c + drc[i][1]; if ( r1 >= 0 && r1 < 8 && c1 >= 0 && c1 < 8 && !vis[r1][c1] ) //选取可走的方向中,没有被访问的位置 { que[tail++] = r1 * 8 + c1; //该位置入队 ans[r1][c1] = ans[r][c] + 1; //更新所走步数 vis[r1][c1] = 1; } } } } int main() { int m, n; char a, b; while ( scanf("%c%d %c%d", &a, &m, &b, &n) != EOF ) { getchar(); //吃到末尾的回车,以免它作为下一组输入的第一个字符 a 被读入 memset( vis, 0, sizeof(vis) ); memset( ans, 0, sizeof(ans) ); bfs(m - 1, a - 'a'); //这样处理,使得 a1 位置的坐标为 (0, 0) printf( "To get from %c%d to %c%d takes %d knight moves. ", a, m, b, n, ans[n - 1][b - 'a'] ); } return 0; }
/* 法二: 参考了: http://blog.csdn.net/rowanhaoa/article/details/7803673 该题是用dfs做的,注意理解递归 */ #include <cstdio> #include <iostream> #define rep(i, n) for ( int i = 0; i < (n); i++ ) using namespace std; int a, b, x, y; int ans; char s1[100], s2[100]; int drc[8][2] = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, -1 }, { 2, 1 }, { -2, 1 }, { -2, -1 } }; bool isin(int a, int x) { return ( a >= 0 && a < 8 && x >= 0 && x < 8 ); } void dfs(int a, int x, int sum) { if (sum >= ans) return; if ( a == b && x == y) { ans = min(ans, sum); return; } rep(i, 8) { int r = a + drc[i][0], c = x + drc[i][1]; if ( isin(r, c) ) dfs(r, c, sum + 1); } } int main() { while (scanf("%s%s", s1, s2) != EOF ) { ans = 6; a = s1[0] - 'a', x = s1[1] - '1'; b = s2[0] - 'a', y = s2[1] - '1'; dfs(a, x, 0); printf( "To get from %s to %s takes %d knight moves. ", s1, s2, ans ); } return 0; }
/*
另外,本题也可用结构体,不过比前两种写法要繁琐一些...链接见下:
http://blog.csdn.net/mobius_strip/article/details/13089747
*/