题解 | #迷宫问题#

#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

bool hasPathImp(int*&maze,int row,int col,int rows,int cols,bool*&visitArr,std::vector<std::pair<int,int>>&ret)
{
    if(row==rows-1&&col==cols-1) //到达迷宫右下角了
    {
        ret.emplace_back(std::make_pair(row,col));
        return true;
    }
    if(row>=0&&row<rows&&col>=0&&col<cols&&!visitArr[row*cols+col]&&maze[row*cols+col]==0)
    {
        visitArr[row*cols+col]=true;
        if(hasPathImp(maze,row-1,col,rows,cols,visitArr,ret)||
        hasPathImp(maze,row+1,col,rows,cols,visitArr,ret)||
        hasPathImp(maze,row,col+1,rows,cols,visitArr,ret)||
        hasPathImp(maze,row,col-1,rows,cols,visitArr,ret))
        {
            ret.emplace_back(std::make_pair(row, col));
            return true;
        }
        else
            visitArr[row*cols+col]=false;
    }
    return false;
}

int main() 
{
    int row,col;
    cin>>row>>col;
    int*maze=new int[row*col];
    bool*visitArr=new bool[row*col]; //是否被访问过标记
    memset(visitArr,0,row*col);
    int temp,index=0;
    while(cin>>temp)
        maze[index++]=temp;
    std::vector<std::pair<int,int>>ret; //保存结果用
    hasPathImp(maze,0,0,row,col,visitArr,ret);
    delete[]maze;
    delete[]visitArr;
    for(auto itor=ret.rbegin();itor!=ret.rend();++itor) //注意需要反向输出
        cout<<"("<<(*itor).first<<","<<(*itor).second<<")"<<"\n";
}
// 64 位输出请用 printf("%lld")