poj2243 Knight Moves（BFS）

题目链接

http://poj.org/problem?id=2243

题意

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

思路

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

代码

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <string>

 #include <queue>

 using namespace std;

 struct Node

 {

     int r, c;

     int steps;

     Node(int r, int c, int s) :r(r), c(c), steps(s) {}

 };

 const int N = ;

 int boasd[N][N];

 int visit[N][N];

 int dir[][] = { {-, -}, {-, -}, {-, }, {-, }, {, -}, {, -}, {, }, {, } };

 string ss, se;

 int sr, sc;

 int er, ec;

 void bfs()

 {

     memset(visit, , sizeof(visit));

     queue<Node> q;

     q.push(Node(sr, sc, ));

     visit[sr][sc] = ;

     while (!q.empty())

     {

         Node node = q.front();

         q.pop();

         if (node.r == er && node.c == ec)

         {

             printf("To get from %s to %s takes %d knight moves.\n", ss.c_str(), se.c_str(), node.steps);

             return;

         }

         for (int i = ; i < ; i++)

         {

             int nr = node.r + dir[i][];

             int nc = node.c + dir[i][];

             if (nr >  && nr <=  && nc >  && nc <=  && !visit[nr][nc])

             {

                 visit[nr][nc] = ;

                 q.push(Node(nr, nc, node.steps + ));

             }

         }

     }

 }

 int main()

 {

     //freopen("poj2243.txt", "r", stdin);

     while (cin >> ss >> se)

     {

         sr = ss[] - '';

         sc = ss[] - 'a' + ;

         er = se[] - '';

         ec = se[] - 'a' + ;

         bfs();

     }

     return ;

 }