求助,样例997
查看原帖
求助,样例997
499177
duanxinghe楼主2022/8/24 10:55
#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,fx,fy,flag[1001][1001],ans[1001][1001],a,b;
queue<int> q,qu;
void bfs(int x,int y) {
    q.push(x),qu.push(y);
    flag[x][y]=1;
    ans[x][y]=0;
    while(!q.empty() && !qu.empty()) {
        int l=q.front(),r=qu.front();
        q.pop(),qu.pop();
        if(l==fx && r==fy) return ;
        for(int i=0; i<4; i++) {
            int tx=l+dx[i],ty=r+dy[i];
            if(tx>=0 && ty>=0 && tx<=1000 && ty<=1000 && flag[tx][ty]==0) {
                flag[tx][ty]=1;
                ans[tx][ty]=ans[l][r]+1;
                q.push(tx),qu.push(ty);
            }
        }
    }
}
int main() {
    cin>>fx>>fy>>n;
    for(int i=1; i<=n; i++) {
        cin>>a>>b;
        a+=500,b+=500;
        flag[a][b]=1;
    }
    bfs(500,500);
    cout<<ans[fx][fy];
    return 0;
}
2022/8/24 10:55
加载中...