POJ 1657-Distance on Chessboard（BFS-多种方向不限步数）

痛定思痛。 2022-06-16 00:56 131阅读 0赞

Distance on Chessboard

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;26931</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9124</td> 
  </tr> 
 </tbody> 
</table>

Description

国际象棋的棋盘是黑白相间的8 \* 8的方格，棋子放在格子中间。如下图所示：  
![1657_1.jpg][]  
王、后、车、象的走子规则如下：

*  王：横、直、斜都可以走，但每步限走一格。  
    
 *  后：横、直、斜都可以走，每步格数不受限制。  
    
 *  车：横、竖均可以走，不能斜走，格数不限。  
    
 *  象：只能斜走，格数不限。

写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。

Input

第一行是测试数据的组数t（0 <= t <= 20）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用"字母-数字"的形式表示，字母从"a"到"h"，数字从"1"到"8"。

Output

对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达,就输出"Inf".

Sample Input

2
    a1 c3
    f5 f8

Sample Output

2 1 2 1
    3 1 1 Inf

Source

[POJ Monthly--2004.05.15 Liu Rujia@POJ][POJ Monthly--2004.05.15 Liu Rujia_POJ]

## 解题思路： ##

其实吧，这个题阿，不用搜索，数学方法计算距离可过。

然后呢，我想乱搞一下试试手，就全都用BFS了。三c⌒っﾟДﾟ)っ

就分情况分别处理四种棋子，记录步数，找到就输出。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    #include <iomanip>
    #include <algorithm>
    #define MAXN 1000
    #define INF 0xfffffff
    using namespace std;
    struct node
    {
        int x,y;
    } s,e;
    int step[MAXN][MAXN];
    int vis[MAXN][MAXN];
    //搜索方向
    int dir1[8][2]= {
        {-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};//八方向
    int dir2[4][2]= {
        {-1,0},{0,1},{1,0},{0,-1}};//四方向直走
    int dir3[4][2]= {
        {-1,-1},{1,-1},{1,1},{-1,1}};//四方向斜走
    /*
    王：横、直、斜都可以走，但每步限走一格。
    后：横、直、斜都可以走，每步格数不受限制。
    车：横、竖均可以走，不能斜走，格数不限。
    象：只能斜走，格数不限。*/
    void bfs()
    {
        bool flag=false;
        //王:横、直、斜都可以走，但每步限走一格
        memset(step,0,sizeof(step));
        memset(vis,false,sizeof(vis));
        queue<node>q;
        q.push(s);
        vis[s.x][s.y]=true;
        while(!q.empty())
        {
            node t=q.front();
            q.pop();
            for(int i=0; i<8; ++i)
            {
                node a;
                a.x=t.x+dir1[i][0];
                a.y=t.y+dir1[i][1];
                if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
                {
                    q.push(a);
                    vis[a.x][a.y]=true;
                    step[a.x][a.y]=step[t.x][t.y]+1;
                }
                if(a.x==e.x&&a.y==e.y)
                {
                    vis[t.x][t.y]=true;
                    step[a.x][a.y]=step[t.x][t.y]+1;
                    cout<<step[e.x][e.y]<<" ";
                    flag=true;//标记可以到达
                    goto B;
                }
            }
        }
        if(!flag) cout<<"Inf ";//无法到达
    B://后：横、直、斜都可以走，每步格数不受限制。
        flag=false;
        memset(step,0,sizeof(step));
        memset(vis,false,sizeof(vis));
        while(!q.empty()) q.pop();//注意清空队列
        q.push(s);
        vis[s.x][s.y]=true;
        while(!q.empty())
        {
            node t=q.front();
            q.pop();
            for(int i=0; i<8; ++i)
            {
                node a;
                a.x=t.x+dir1[i][0];//先走一步
                a.y=t.y+dir1[i][1];
                while(1)//每步格数不受限制
                {
                    if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;//超出限制
                    if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
                    {
                        q.push(a);
                        vis[a.x][a.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                    }
                    if(a.x==e.x&&a.y==e.y)
                    {
                        vis[t.x][t.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                        cout<<step[e.x][e.y]<<" ";
                        flag=true;
                        goto C ;
                    }
                    a.x+=dir1[i][0];//可以在该方向上继续走
                    a.y+=dir1[i][1];
                }
            }
        }
        if(!flag) cout<<"Inf ";
    C://车：横、竖均可以走，不能斜走，格数不限。
        flag=false;
        memset(step,0,sizeof(step));
        memset(vis,false,sizeof(vis));
        while(!q.empty()) q.pop();
        q.push(s);
        vis[s.x][s.y]=true;
        while(!q.empty())
        {
            node t=q.front();
            q.pop();
            for(int i=0; i<4; ++i)
            {
                node a;
                a.x=t.x+dir2[i][0];
                a.y=t.y+dir2[i][1];
                while(1)
                {
                    if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;
                    if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
                    {
                        q.push(a);
                        vis[a.x][a.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                    }
                    if(a.x==e.x&&a.y==e.y)
                    {
                        vis[a.x][a.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                        cout<<step[e.x][e.y]<<" ";
                        flag=true;
                        goto D ;
                    }
                    a.x+=dir2[i][0];
                    a.y+=dir2[i][1];
                }
            }
        }
        if(!flag) cout<<"Inf ";
    D: //象：只能斜走，格数不限
        flag=false;
        memset(step,0,sizeof(step));
        memset(vis,false,sizeof(vis));
        while(!q.empty()) q.pop();
        q.push(s);
        vis[s.x][s.y]=true;
        while(!q.empty())
        {
            node t=q.front();
            q.pop();
            for(int i=0; i<4; ++i)
            {
                node a;
                a.x=t.x+dir3[i][0];
                a.y=t.y+dir3[i][1];
                while(1)
                {
                    if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;
                    if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
                    {
                        q.push(a);
                        vis[a.x][a.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                    }
                    if(a.x==e.x&&a.y==e.y)
                    {
                        vis[a.x][a.y]=true;
                        step[a.x][a.y]=step[t.x][t.y]+1;
                        cout<<step[e.x][e.y]<<endl;
                        flag=true;
                        return ;
                    }
                    a.x+=dir3[i][0];
                    a.y+=dir3[i][1];
                }
            }
        }
        if(!flag) cout<<"Inf"<<endl;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T;
        cin>>T;
        while(T--)
        {
            char ch;
            int t;
            cin>>ch>>t;
            s.y=ch-'a',s.x=t-1;
            cin>>ch>>t;
            e.y=ch-'a',e.x=t-1;
            if(s.x==e.x&&s.y==e.y) cout<<"0 0 0 0"<<endl;//注意同起终点时必须特判
            else bfs();
        }
        return 0;
    }

[1657_1.jpg]: /images/20220616/427abf365e0d4d729a6965cfd0a5995e.png
[POJ Monthly--2004.05.15 Liu Rujia_POJ]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2004.05.15+Liu+Rujia%40POJ