题目描述

BFS模板题

算法1

#include <iostream>
#include <algorithm>
#include <queue> 
using namespace std;
const int N = 110;
int n,m;
int maps[N][N];
int vis[N][N];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct node{
    int x;
    int y;
    int step;
};
queue<node>yubo;
void bfs(node r)
{
    vis[r.x][r.y] = 1;
    yubo.push(r);
    while(yubo.size())
    {
        node f = yubo.front();
        yubo.pop();
        if(f.x == n && f.y == m)
            cout << f.step << endl;
        for (int k = 0; k < 4; k ++ )
        {
            int fx = dx[k] + f.x;
            int fy = dy[k] + f.y;
            if(fx <= 0 || fx > n || fy <= 0 || fy > m || vis[fx][fy] == 1 || maps[fx][fy] == 1)
                continue;
            vis[fx][fy] = 1;
            node pp ;
            pp.x = fx;
            pp.y = fy;
            pp.step = f.step + 1;
            yubo.push(pp);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            cin >> maps[i][j];
        } 
    }
    node p;
    p.x = 1,p.y = 1;
    p.step = 0;
    bfs(p);
    return 0;
}

```