题解 | #迷宫问题#

这题目难度标中等？？

递归还是有难度啊。。。

#include #include #include using namespace std; struct point{ int x; int y; }; int N,M; void dfs(vector<vector>&maze,vector&path,vector&res,point& p) { if((p.x==M-1)&&(p.y==N-1)) { res=path; return; } //向上

if(((p.y-1)<N)&&((p.y-1)>=0)&&maze[p.y-1][p.x]==0)
{if(path.size()>1)
    {if(p.y-1!=path[path.end()-path.begin()-2].y)
{   point temp = {p.x,p.y-1}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
 path.pop_back();
}
    }
else

{ point temp = {p.x,p.y-1}; path.push_back(temp); dfs(maze,path,res,temp); path.pop_back(); }} //向下

if(((p.y+1)<N)&&(p.y+1)>=0&&maze[p.y+1][p.x]==0)
     if(path.size()>1){
        if(p.y+1!=path[path.end()-path.begin()-2].y)
{   point temp = {p.x,p.y+1}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
     path.pop_back();
}}
else
{
     point temp = {p.x,p.y+1}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
     path.pop_back();
}
    if(((p.x+1)<M)&&(p.x+1)>=0&&maze[p.y][p.x+1]==0)
    if(path.size()>1)
    {if(p.x+1!=path[path.end()-path.begin()-2].x)
{   point temp = {p.x+1,p.y}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
 path.pop_back();
}}
else
     {   point temp = {p.x+1,p.y}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
 path.pop_back();
}
        if(((p.x-1)<M)&&(p.x-1)>=0&&maze[p.y][p.x-1]==0)
    if(path.size()>1)
    {if(p.x-1!=path[path.end()-path.begin()-2].x)
{   point temp = {p.x-1,p.y}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
 path.pop_back();
}
    }
else
{ point temp = {p.x-1,p.y}; 
    path.push_back(temp);
    dfs(maze,path,res,temp);
 path.pop_back();}
return;

} int main() {

while(cin>>N>>M){
vector<vector<int>>maze(N,vector<int>(M,0));
for(int i=0;i<N;i++)
    for(int j=0;j<M;j++)
    {
        cin>>maze[i][j];
    }
vector<point> path;
path.push_back({0,0});
vector<point>res;
point p ={0,0};
dfs(maze,path,res,p);
for(int i=0 ;i<res.size();i++){
    p=res[i];
cout<<'('<<p.y<<','<<p.x<<')'<<endl;
}

}
return 0;

}