给一个题目，求这个最短的路径的点的路径

解法:看ppt



代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct node{int x,y;};
const int N = 120;
int g[N][N];
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
node c[N][N];
void print(int x,int y)
{
    if(x==0&&y==0)
    {
        return;
    }
    auto q=c[x][y];
    print(q.x,q.y);
    cout << x<<" "<<y<<endl;
}
void dfs(int x,int y)
{
    queue<node> p;
    p.push({x,y});
    g[x][y]=1;
    while(p.size())
    {
        auto t=p.front();
        p.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(x<0||x>=n||y<0||y>=m||g[x][y])
            {
                continue;
            }
            c[x][y]=t;//将这个点的前驱节点进行标记
            g[x][y]=1;
            p.push({x,y});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    dfs(0,0);
    puts("0 0");
    print(n-1,m-1);
    return 0;
}