最少步数（bfs）

蔚落 2022-08-02 04:59 140阅读 0赞

## 最少步数 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 4

描述

这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1  
 1,0,0,1,0,0,1,0,1  
 1,0,0,1,1,0,0,0,1  
 1,0,1,0,1,1,0,1,1  
 1,0,0,0,0,1,0,0,1  
 1,1,0,1,0,1,0,0,1  
 1,1,0,1,0,1,0,0,1  
 1,1,0,1,0,0,0,0,1  
 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据;  
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
    3 1  5 7
    3 1  6 7

样例输出

12
    11

来源

[\[苗栋栋\]原创][Link 1]

上传者

[苗栋栋][Link 2]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    int map[9][9]={
        {1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,1,0,1},
        {1,0,0,1,1,0,0,0,1},
        {1,0,1,0,1,1,0,1,1},
        {1,0,0,0,0,1,0,0,1},
        {1,1,0,1,0,1,0,0,1},
        {1,1,0,1,0,1,0,0,1},
        {1,1,0,1,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1}
        };
    int vis[9][9];
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    int n,a,b,c,d;
    struct node
    {
        int x;
        int y;
        int step;
    };
    int check(int x,int y)
    {
        if(x<0||x>=9||y<0||y>=9)
        {
            return 1;
        }
        if(vis[x][y]||map[x][y]==1)
        {
            return 1;
        }
        return 0;
    }
    int bfs()
    {
        int i;
        queue<node>Q;
        node rencent,next;
        rencent.x=a;
        rencent.y=b;
        rencent.step=0;
        vis[rencent.x][rencent.y]=1;
        Q.push(rencent);
        while(!Q.empty())
        {
            rencent=Q.front();
            Q.pop();
            if(rencent.x==c&&rencent.y==d)
            {
                return rencent.step;
            }
            for(i=0;i<4;i++)
            {
                next=rencent;
                next.x+=dir[i][0];
                next.y+=dir[i][1];
                if(check(next.x,next.y))
                {
                    continue;
                }
                next.step=rencent.step+1;
                vis[next.x][next.y]=1;
                Q.push(next);
            }
        }
    
    }
    int main()
    {
        cin>>n;
        while(n--)
        {
            memset(vis,0,sizeof(vis));
            cin>>a>>b>>c>>d;
            cout<<bfs()<<endl;
        }
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E8%8B%97%E6%A0%8B%E6%A0%8B%5D%E5%8E%9F%E5%88%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E8%8B%97%E6%A0%8B%E6%A0%8B