重铸华农荣光 我辈义不容辞

the fifteenth day-bfs

第一次见面

#include<iostream>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=110;
int g[N][N],f[N][N],n,m;

int bfs(int x,int y)
{
    queue<PII> que;
    que.push({x,y});

    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(!que.empty()){
        PII t=que.front();
        que.pop();
        g[t.first][t.second]=1;
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&b>=0&&a<n&&b<m&&!g[a][b]){
                g[a][b]=1;
                f[a][b]=f[t.first][t.second]+1;
                que.push({a,b});
            }
        }
    }

    return f[n-1][m-1];
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];

    cout<<bfs(0,0);
    return 0;
}