爆0了，9MLE,1WA蒟蒻求助

B1ade_ @ 2021-03-02 21:27:29

#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
int x,y,xe,ye,n;
struct node
{
    int x,y,d;
};
queue<node>q;
int ne[4]={1,0,-1,0},nx[4]={0,1,0,-1},minn[1005][1005];
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        string st;cin>>st;
        for (int j=1;j<=n;++j)
        {
            a[i][j]=st[j-1]-'0';
        }
    }
    cin>>x>>y>>xe>>ye;
    for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) minn[i][j]=INT_MAX;
    node n11;n11.d=0;n11.x=1;n11.y=1;
    q.push(n11);
    while (q.size())
    {
        if (q.front().x==xe&&q.front().y==ye)
        {
            break;
        }
        for (int i=0;i<4;++i)
        {
            int xx=q.front().x+ne[i],yy=q.front().y+nx[i];
            if (xx>=1&&xx<=n&&yy>=1&&yy<=n&&!a[xx][yy]&&q.front().d+1<=minn[xx][yy])
            {
                node n12;n12.x=xx;n12.y=yy;n12.d=q.front().d+1;minn[xx][yy]=n12.d;
                q.push(n12);
            }
        }
        q.pop();
    }
    cout<<q.front().d;
    return 0;
}

by FCB_1899 @ 2021-03-02 21:58:27

minn根本用不着啊，直接广搜，如果搜到了终点就一定是最短路啊

by B1ade_ @ 2021-03-02 22:04:26

谢谢dalao 但是还是0分

by FCB_1899 @ 2021-03-02 22:07:26

#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
int x,y,xe,ye,n;
struct node
{
    int x,y,d;
};
queue<node>q;
int ne[]={1,0,-1,0},nx[]={0,1,0,-1};
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        string st;cin>>st;
        for (int j=1;j<=n;++j)
        {
            a[i][j]=st[j-1]-'0';
        }
    }
    cin>>x>>y>>xe>>ye;
    node n11;n11.d=0;n11.x=x;n11.y=y;
    q.push(n11);
    while (!q.empty())
    {
        node t=q.front();
        q.pop();
        if (t.x==xe&&t.y==ye)
        {
            cout<<t.d;
            return 0;
        }
        for (int i=0;i<4;++i)
        {
            int xx=t.x+ne[i],yy=t.y+nx[i];
            if (xx>=1&&xx<=n&&yy>=1&&yy<=n&&!a[xx][yy])
            {
                node n12;n12.x=xx;n12.y=yy;n12.d=t.d+1;
                q.push(n12);
                a[xx][yy]=1;
            }
        }
    }
    return 0;
}

给你改对了 @RAINDEER

by FCB_1899 @ 2021-03-02 22:08:34

另外，我认为万能头是一种极劣的癖好

by ____OccDreamer @ 2021-03-03 18:30:40

@RAINDEER 不要问怎么写的，代码太古早了。（你看都没有用万能头

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
char c[2010][2010];
int n,x1,y1,x2,y2;bool f=0;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int h=0,t=0;
struct st
{
    int x;
    int y;
    int s;
}q[10000010];
void bfs(int a,int b)
{
    while (h<t)
    {
        for (int i=0;i<4;++i)
        {
            int nx=q[h].x+dx[i];
            int ny=q[h].y+dy[i];
            if (nx>=1&&nx<=n&&ny>=1&&ny<=n&&c[nx][ny]!='1')
            {
                if (nx==a&&ny==b) {cout<<q[h].s+1;return ;}
                c[nx][ny]='1';
                q[t].x=nx;
                q[t].y=ny;
                q[t++].s=q[h].s+1;
            }
        }
        ++h;
    }
}

int main()
{

    cin>>n;
    for (int i=1;i<=n;++i)
    for (int j=1;j<=n;++j) cin>>c[i][j];
    cin>>x1>>y1>>x2>>y2;
    q[t].x=x1;
    q[t].s=0;
    q[t++].y=y1;
    c[x1][y1]='1';
    bfs(x2,y2);
    return 0;
}

by B1ade_ @ 2021-03-14 21:48:53

谢谢dalao们