poj2243 Knight Moves（BFS）

题目链接

题意

输入8*8国际象棋棋盘上的两颗棋子（a~h表示列，1~8表示行），求马从一颗棋子跳到另一颗棋子需要的最短路径。

思路

使用bfs求解，注意国际象棋中马的走法。

代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #include <queue>
 6 using namespace std;
 7 
 8 struct Node
 9 {
10     int r, c;
11     int steps;
12 
13     Node(int r, int c, int s) :r(r), c(c), steps(s) {}
14 };
15 
16 const int N = 10;
17 int boasd[N][N];
18 int visit[N][N];
19 int dir[8][2] = { {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2} };
20 string ss, se;
21 int sr, sc;
22 int er, ec;
23 
24 void bfs()
25 {
26     memset(visit, 0, sizeof(visit));
27     queue<Node> q;
28     q.push(Node(sr, sc, 0));
29     visit[sr][sc] = 1;
30     while (!q.empty())
31     {
32         Node node = q.front();
33         q.pop();
34         if (node.r == er && node.c == ec)
35         {
36             printf("To get from %s to %s takes %d knight moves.
", ss.c_str(), se.c_str(), node.steps);
37             return;
38         }
39         for (int i = 0; i < 8; i++)
40         {
41             int nr = node.r + dir[i][0];
42             int nc = node.c + dir[i][1];
43             if (nr > 0 && nr <= 8 && nc > 0 && nc <= 8 && !visit[nr][nc])
44             {
45                 visit[nr][nc] = 1;
46                 q.push(Node(nr, nc, node.steps + 1));
47             }
48         }
49     }
50 }
51 
52 int main()
53 {
54     //freopen("poj2243.txt", "r", stdin);
55     while (cin >> ss >> se)
56     {
57         sr = ss[1] - '0';
58         sc = ss[0] - 'a' + 1;
59         er = se[1] - '0';
60         ec = se[0] - 'a' + 1;
61         bfs();
62     }
63     return 0;
64 }