题解 | #迷宫问题#

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Point1
{
    int x, y;
    Point1(int x,int y):x(x),y(y){};
    Point1(){};
};



int m1[10][10];
Point1 m2[10][10];
vector<Point1> ans1;

inline bool check(int m,int n,int y,int x)
{
    if(0<=y&&0<=x&&y<m&&x<n)
        return true;
    return false;
}

void dfs(Point1 a1,int m,int n)
{
    queue<Point1> q1;
    q1.push(a1);
    while(!q1.empty())
    {
        Point1 tmp=q1.front();q1.pop();
        int x=tmp.x,y=tmp.y;
        m1[y][x]=1;
        if(x==n-1&&y==m-1)
            break;
        if(check(m,n,y-1,x)&&m1[y-1][x]==0)
        {

            m2[y-1][x]=Point1(x,y);
            q1.push(Point1(x,y-1));
        }
        if(check(m,n,y+1,x)&&m1[y+1][x]==0)
        {

            m2[y+1][x]=Point1(x,y);
            q1.push(Point1(x,y+1));
        }
        if(check(m,n,y,x-1)&&m1[y][x-1]==0)
        {

            m2[y][x-1]=Point1(x,y);
            q1.push(Point1(x-1,y));
        }
        if(check(m,n,y,x+1)&&m1[y][x+1]==0)
        {

            m2[y][x+1]=Point1(x,y);
            q1.push(Point1(x+1,y));
        }
            
    }

}
void addList(Point1 a)
{
    if(a.x==0&&a.y==0)
    {
        ans1.push_back(a);
        return;
    }
    ans1.push_back(a);
    addList(m2[a.y][a.x]);
}

//reverse
//printf



int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        ans1.clear();
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                cin>>m1[i][j];
        dfs(Point1(0,0),m,n);
        addList(Point1(n-1,m-1));
        reverse(ans1.begin(),ans1.end());
        for(Point1 a:ans1)
        {
            printf("(%d,%d)\n",a.y,a.x);
        }
        
    }
}