广搜 WA 0 求助

违规用户名1053866 @ 2024-10-27 16:13:23

#include<bits/stdc++.h>
using namespace std;
int n,m,mp[1005][1005],dx[4]={1,0,-1,0},dy[4]={0,-1,0,1},ans=INT_MAX,x3,y3,x4,y4;
bool v[1005][1005];
struct node{
    int x,y,step;
};
queue<node> q;
void bfs(){
    node a={x3,y3,0};
    q.push(a);
    while(!q.empty()){
        node f=q.front();
        q.pop();
        if(f.x==x4&&f.y==y4){
            if(f.step<ans)
                ans=f.step;
            return;
        }
        for(int i=0;i<4;i++){
            int xx=f.x+dx[i],yy=f.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]==0&&v[xx][yy]==0){
                node f1={xx,yy,f.step+1};
                q.push(f1);
                v[xx][yy]=1;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    }
    cin>>x3>>y3>>x4>>y4;
    v[1][1]=1;
    bfs();
    cout<<ans;
}

by __zyy_wgcs__ @ 2024-10-27 16:44:51

改了几个地方

#include<bits/stdc++.h>
using namespace std;
int n,m,mp[2005][2005],dx[]={1,0,-1,0},dy[]={0,-1,0,1},ans=INT_MAX,x3,y3,x4,y4;
bool v[2005][2005];
struct node{
    int x,y,step;
};
queue<node> q;
void bfs(){
    node a={x3,y3,0};
    q.push(a);
    while(!q.empty()){
        node f=q.front();
        q.pop();
        if(f.x==x4&&f.y==y4){
            if(f.step<ans)
                ans=f.step;
            return;
        }
        for(int i=0;i<4;i++){
            int xx=f.x+dx[i],yy=f.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]==0&&v[xx][yy]==0){
                node f1={xx,yy,f.step+1};
                q.push(f1);
                v[xx][yy]=1;
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            scanf("%1d",&mp[i][j]);//一个数字一个数字的读入
    }
    cin>>x3>>y3>>x4>>y4;
    v[x3][y3]=1;//初始点
    bfs();
    cout<<ans;
    return 0;//记得写
}