文件目录

#include <bits/stdc++.h>
using namespace std;
int n = 5, m = 5;
int c[105][105];
int fat[105][105];
struct node
{
    int x, y, step;
};
int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1};
int bfs(int x, int y)
{
    queue<node> q;
    q.push((node){x, y, 1});
    bool vis[105][105] = {};
    vis[x][y] = true;
    while (!q.empty())
    {
        node u = q.front();
        q.pop();
        if (u.x == n - 1 && u.y == m - 1)
        {
            return u.x * 5 + u.y;
        }
        for (int i = 0; i < 4; i++)
        {
            int xx = u.x + dir[i][0];
            int yy = u.y + dir[i][1];
            if (xx >= 0 && yy >= 0 && xx < n && yy < m && vis[xx][yy] == false && c[xx][yy] != 1)
            {
                vis[xx][yy] = true;
                fat[xx][yy] = u.x * 5 + u.y;
                q.push((node){xx, yy, u.step + 1});
            }
        }
    }
    return -1;
}
void f(int num)
{
    int y = num % 5;
    int x = num / 5;
    if (!(x == 0 && y == 0))
        f(fat[x][y]);
    printf("(%d, %d)\n", x, y);
}
int main()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> c[i][j];
    int ans = bfs(0, 0);
    // cout<<ans/5<<" "<<ans%5<<endl;
    f(ans);
    /*for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            int k=fat[i][j];
            cout<<k/5<<","<<k%5<<" ";
        }
        cout<<endl;
    }*/
    return 0;
}