跳马(Knight Moves), ZOJ1091, POJ2243 x

跳马(Knight Moves), ZOJ1091, POJ2243

题目描述：

给定象棋棋盘上两个位置 a 和 b，编写程序，计算马从位置 a 跳到位置 b 所需步数的最小值。

输入描述：

输入文件包含多个测试数据。每个测试数据占一行，为棋盘中的两个位置，用空格隔开。棋盘位置为两个字符组成的串，第 1 个字符为字母 a～h，代表棋盘中的列；第 2 个字符为数字字符1～8，代表棋盘中的行。

输出描述：

对输入文件中的每个测试数据，输出一行"To get from xx to yy takes n knight moves."， xx 和yy 分别为输入数据中的两个位置， n 为求得的最少步数。

样例输入：

样例输出：

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.

这道题其实就是裸的bfs

不过需要注意的是：输入输出的形式！

代码如下：

1）注释版：

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 char s[];

 bool v[][];

 int ex,ey,sx,sy,ans;

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

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

 struct node

 {

     int x,y,step;

 }cur,nxt;

 queue<node>q;

 void bfs()

 {

     if(ex==sx&&ey==sy) //特判起点等于终点

     {

             printf("To get from %c%d to %c%d takes %d knight moves.\n",char(ex+'a'-),ey,char(sx+'a'-),sy,);

             return;

     }

     while(!q.empty()) q.pop();  // 多组数据初始化

     memset(v,,sizeof(v));      // 同上

     cur.x=ex,cur.y=ey; cur.step=; //起点

     v[ex][ey]=true; //不要漏了标记起点

     q.push(cur);

     while(!q.empty())

     {

         cur=q.front();

         q.pop(); //不要漏了当前出队

          //v[cur.x][cur.y]=false; 出队，清楚标记，是否需要？ 答案当然是否定的

         for(int i=;i<;i++) //八方位搜索

         {

             int xx=cur.x+dx[i],yy=cur.y+dy[i];

             if(xx>&&xx<=&&yy>&&yy<=&&!v[xx][yy])

             {

                 if(xx==sx&&yy==sy) //如果找到了，第一个找到的一定就是最近的

                 {

                     printf("To get from %c%d to %c%d takes %d knight moves.\n",char(ex+'a'-),ey,char(sx+'a'-),sy,cur.step+);

                     return ;//必须用return，或者也可以用多次break

                 }

                 nxt.x=xx, nxt.y=yy; nxt.step=cur.step+;

                 v[nxt.x][nxt.y]=true;//标记

                 q.push(nxt); //将扩展出的状态入队

             }

         }

     }

 }

 int main()

 {

     while(scanf("%s",s)!=EOF)

     {

         ex=s[]-'a'+; ey=s[]-'';

         scanf("%s",s);

         sx=s[]-'a'+; sy=s[]-'';

         bfs();

     }

 }

2）非注释版：（另一种方法，表示方向的换为一个二维数组）

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 struct node

 {

     int x,y;

 };

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

 int dis[][];

 int ex,ey;

 bool OK(node &b)

 {

     if(b.x<||b.x>||b.y<||b.y>||dis[b.x][b.y])

       return false;

     return true;

 }

 void BFS(int x,int y)

 {

     node a,b;

     queue<node> Q;

     a.x=x;a.y=y;

     Q.push(a);

     int i;

     while(!Q.empty())

     {

         a=Q.front();Q.pop();

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

         {

             b.x=a.x+dir[i][];

             b.y=a.y+dir[i][];

             if(b.x==x&&b.y==y) continue;

             if(OK(b))

              {

                  dis[b.x][b.y]=dis[a.x][a.y]+;

                  Q.push(b);

              }

             if(b.x==ex&&b.y==ey) return;

         }

     }

 }

 int main()

 {

    char op1[],op2[];

    while(scanf("%s %s",op1,op2)!=EOF)

    {

        memset(dis,,sizeof(dis));

        int x=op1[]-'a'+,y=op1[]-'';

        ex=op2[]-'a'+;ey=op2[]-'';

      //  printf("%d %d==\n",ex,ey);

        if(x!=ex||y!=ey)

          BFS(x,y);

     printf("To get from %s to %s takes %d knight moves.\n",op1,op2,dis[ex][ey]);

    }

 }

巴特西

跳马(Knight Moves), ZOJ1091, POJ2243 x

最新文章

热门文章