算法1

(反向搜索)

从结尾到开头搜索，避免了缓存队列

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;
#define x first
#define y second
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int g[N][N];
int n;
PII q[M],pre[N][N];
void bfs(int x,int y)
{
    memset(pre,-1,sizeof pre);
    int hh=0,tt=0;
    q[hh]={x,y};
    tt++;
    while(hh<tt)
    {
        PII p=q[hh];
        hh++;
        for(int i=0;i<4;i++)
        {
            int a=p.x+dx[i],b=p.y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<n&&pre[a][b].x==-1&&g[a][b]==0)
            {
                pre[a][b]=p;
                q[tt++]={a,b};
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    bfs(n-1,n-1);
    PII end={0,0};
    while(true)
    {
        cout<<end.x<<" "<<end.y<<endl;
        if(end.x==n-1&&end.y==n-1) break;
        end=pre[end.x][end.y];
    }
    return 0;
}

算法2

(正向搜索)

才左上角到右下角，需要用一个队列来缓存路径，然后输出。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;
#define x first
#define y second
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int g[N][N];
int n;
PII q[M],pre[N][N];
void bfs(int x,int y)
{
    memset(pre,-1,sizeof pre);
    int hh=0,tt=0;
    q[hh]={x,y};
    tt++;
    while(hh<tt)
    {
        PII p=q[hh];
        hh++;
        for(int i=0;i<4;i++)
        {
            int a=p.x+dx[i],b=p.y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<n&&pre[a][b].x==-1&&g[a][b]==0)
            {
                pre[a][b]=p;
                q[tt++]={a,b};
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    bfs(0,0);
    PII end={n-1,n-1};
    int tt=0;
    while(true)
    {
        q[tt++]={end.x,end.y};
        if(end.x==0&&end.y==0) break;
        end=pre[end.x][end.y];
    }
    for(int i=tt-1;i>=0;i--)
        cout<<q[i].x<<" "<<q[i].y<<endl;
    return 0;
}