一. 题目

二. 理论

• 因为BFS每次都是向外扩展一层，利用这一特性，可以求解最短路问题

• 本题思路：bfs+用一个pre[x][y]数组，存储从哪个点到的(x, y)，逆序向前推出路径。

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e3+10;
using PII=pair<int, int>;

int n;
int g[N][N];

class Search
{
public://下标偏移量
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
    int d[N][N], hh, tt;//最短路数组
    PII q[N*N], pre[N][N];//点队列, 和记录前向点数组
public:
    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    Search()
    {
        initIO(), hh=0, tt=-1;//最开始
        fill(d[0], d[0]+N*N, 1e9);
    }

    //返回最短的整个路径
    vector<PII> bfs()
    {
        q[++tt]={0, 0}, d[0][0]=0;

        while(hh<=tt)
        {
            PII t=q[hh++];
            int x=t.first, y=t.second;
            if(x==n-1&&y==n-1) break;//第一次到达终点，就是最短路

            for(int i=0;i<4;++i)
            {
                int a=x+dx[i], b=y+dy[i];//若越界，或是墙无法走，或已经是最短，跳过
                if(a<0||a>n-1||b<0||b>n-1||g[a][b]||d[a][b]<=d[x][y]+1) continue;
                q[++tt]={a, b}, pre[a][b]=t, d[a][b]=d[x][y]+1;
            }
        }

        int x=n-1, y=n-1;
        vector<PII> path;
        path.reserve(n*n);
        while(x!=0||y!=0)
        {
            path.emplace_back(x, y);//调用pair(x, y)构造函数
            PII p=pre[x][y];
            x=p.first, y=p.second;
        }
        path.emplace_back(0, 0);//调用pair(0, 0)构造函数
        reverse(path.begin(), path.end());//翻转

        return path;
    }
}s;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin>>g[i][j];

 
//    捕获列表只用于局部非static变量，lambda可以直接使用局部static变量
//    和它所在函数之外声明的名字, 参数列表和返回值可省略
    vector<PII> ans=s.bfs();
    for_each(ans.begin(), ans.end(),
             [](const PII &item)
             {
                cout<<item.first<<" "<<item.second<<endl;
             });
}