BFS蒟蒻求助

Li_wenjie @ 2021-11-14 23:46:59

#include<bits/stdc++.h>
using namespace std;
int ans[1001][1001];
bool notok[1001][1001];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
struct Node
{
    int x,y;
    Node(int _x,int _y)
    {
        x=_x,y=_y;
    }
};
int main()
{
    memset(ans,-1,sizeof(ans));
//  cout<<ans[313][313];
    queue<Node> s;
    int n;
    cin>>n;
    int m=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%1d",&notok[i][j]);
    int x,y,x1,y1;
    cin>>x>>y>>x1>>y1; 
    Node first(x,y);
    s.push(first);
    ans[x][y]=0;
    bool pd=0;
    while(!s.empty())
    {
        Node now=s.front();
        s.pop();
        int _x=now.x;
        int _y=now.y;
        int step=ans[_x][_y];
        for(int i=0;i<=7;i++)
        {
            int xx=_x+dx[i];
            int yy=_y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&ans[xx][yy]==-1&&!notok[xx][yy]) 
            {
                Node newnode(xx,yy);
                s.push(newnode);
                ans[xx][yy]=step+1;
            }
        }
    }
    cout<<ans[x1][y1];
}

by DNWy @ 2021-11-15 07:52:12

改后AC代码:

#include<bits/stdc++.h>
using namespace std;
int ans[1001][1001];
bool notok[1001][1001];
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,-1,1};
struct Node
{
    int x,y;
    Node(int _x,int _y)
    {
        x=_x,y=_y;
    }
};
string str;

int main()
{
    // freopen("data.in","r",stdin);
    memset(ans,-1,sizeof(ans));
    queue<Node> s;
    int n;
    cin>>n;
    int m=n;
    for(int i=1;i<=n;i++){
        cin>>str;
        for(int j=0;j<n;++j)
            notok[i][j+1]=str[j]-48;
    }
    int x,y,x1,y1;
    cin>>x>>y>>x1>>y1; 
    Node first(x,y);
    s.push(first);
    ans[x][y]=0;
    while(!s.empty())
    {
        Node now=s.front();s.pop();
        int _x=now.x,_y=now.y,step=ans[_x][_y];

        for(int i=0;i<=3;i++)
        {
            int xx=_x+dx[i],yy=_y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&ans[xx][yy]==-1&&!notok[xx][yy]) 
            {
                Node newnode(xx,yy);
                s.push(newnode);
                ans[xx][yy]=step+1;
            }
        }
    }
    cout<<ans[x1][y1]<<"\n";
}

主要改动:

1. 采用string读入01串,再转成bool数组
2. BFS$转移仅上下左右移动$4$个方向,故循环为$0\rightarrow 3

另外,不建议使用y_1这种变量名,容易撞保留字(其在math.h中是一个被定义的变量)

给一份我写的代码

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int x,y,s;
}s,t;
int n,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool g[1010][1010];
string str;
queue<Node> q;

void BFS(){
    g[s.x][s.y]=1;
    q.push(s);
    while(!q.empty()){
        Node now=q.front();q.pop();

        for(int i=0;i<4;++i){
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx==t.x&&ny==t.y){
                cout<<now.s+1<<"\n";
                exit(0);
            }
            if(nx>0&&nx<=n&&ny>0&&ny<=n&&!g[nx][ny]){
                g[nx][ny]=1;
                q.push((Node){nx,ny,now.s+1});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    // freopen("data.in","r",stdin);

    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>str;
        for(int j=0;j<n;++j)
            g[i][j+1]=str[j]-48;
    }
    cin>>s.x>>s.y>>t.x>>t.y;

    BFS();

    return 0;
}

by Li_wenjie @ 2021-11-16 21:57:29

多谢大佬！！！！