迷宫问题 XDOJ

标题
迷宫问题  
时间限制
1 S 
内存限制
10000 Kb 
问题描述 
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
问题输入 
一组数据，输入数据第1行为两个正整数m和n，m表示迷宫高度，n表示迷宫宽度，m<100,n<100；第2行为两个整数，分表表示起点的行列位置；第3为两个整数，分别表示终点的行列位置；其后为m行数据，每行n个整数，表示迷宫对应位置的状态，0表示通路，1表示障碍。 
问题输出 
以三元组(i,j,d)形式输出从起点到终点搜索到的第一条通路，没有则输出no。其中三元组中的(i,j)表示迷宫中的一个坐标，d表示走到下一坐标的方向，d=1表示向右走，d=2为向下走，d=3为向左走，d=4为向上走。
输入样例 
8 8
1 1
8 8
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 0 
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0
 
输出样例 
(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),(4,1,2),(5,1,1),(5,2,1),(5,3,2),(6,3,1),(6,4,1),(6,5,2),(7,5,2),(8,5,1),(8,6,1),(8,7,1),(8,8,1) 

这道题生成一条路径，可以使用深度优先搜索算法+回溯，利用递归去生成路径。

//输出所有路径
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
using Triple=tuple<int,int,int>;
class PathFinder{
    int startx,starty,endx,endy;
    //右1下2左3上4
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    vector<Triple> path;
    vector<vector<int>> map;
    vector<vector<int>> visit;
public:
    PathFinder(vector<vector<int>>& map):map(map){}
    void input(int a,int b,int c,int d){
        startx=a;starty=b;
        endx=c;endy=d;
    }
    bool res=false;//表示是否找到第一条路经
    void dfs(int x,int y){
        if(res) return;
        if(x==endx-1&&y==endy-1){
            res=true;
            return;
        }
        for(int i=0;i<4;i++){
            int tx,ty;
            tx=x+dx[i];
            ty=y+dy[i];
            // map中1表示障碍 10表示通路
            if((tx>=0&&tx<map.size()&&ty>=0&&ty<map[tx].size())&&(!map[tx][ty])&&(!visit[tx][ty])){
                visit[tx][ty]=1;
                path.emplace_back(tx+1,ty+1,i+1);
                dfs(tx,ty);
                if(res) return;
                visit[tx][ty]=0;//回溯
                path.pop_back();
            }
        }
    }
    vector<Triple> Pathfind(){
        visit.resize(map.size(),vector<int>(map[0].size(),0));//0表示未访问 1表示已访问
        visit[startx-1][starty-1]=1;
        path.emplace_back(startx,starty,1);
        dfs(startx-1,starty-1);
        return path;
    }
};
int main()
{
    int m,n,startx,starty,endx,endy;
    cin>>m>>n>>startx>>starty>>endx>>endy;

    vector<vector<int>> map(m,vector<int>(n,0));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>map[i][j];
        }
    }

    PathFinder pf(map);
    pf.input(startx,starty,endx,endy);
    vector<Triple> path=pf.Pathfind();
    int i=0;
    if(path.size()==1){
        cout<<"no";
        i++;//使后面的for循环不会运行
    }
    for(;i<path.size();i++){
        if(i<path.size()-1){
            cout<<"("<<get<0>(path[i])<<","<<get<1>(path[i])
                <<","<<get<2>(path[i+1])<<")"<<",";
            continue;
        }
        cout<<"("<<get<0>(path[i])<<","<<get<1>(path[i])
            <<","<<"1"<<")";
    }
    return 0;
}

在此基础上，我结合了在B站上看的一些UP主的视频，写了生成所有路径的算法：

//输出所有路径
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
using Triple=tuple<int,int,int>;
class PathFinder{
    int startx,starty,endx,endy;
    //右1下2左3上4
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    vector<Triple> path;
    vector<vector<Triple>> path_sum;
    vector<vector<int>> map;
    vector<vector<int>> visit;
public:
    PathFinder(vector<vector<int>>& map):map(map){}
    void input(int a,int b,int c,int d){
        startx=a;starty=b;
        endx=c;endy=d;
    }
    void dfs(int x,int y){
        if(x==endx-1&&y==endy-1){
            path_sum.push_back(path);
            return;
        }
        for(int i=0;i<4;i++){
            int tx,ty;
            tx=x+dx[i];
            ty=y+dy[i];
            // map中1表示障碍 10表示通路
            if((tx>=0&&tx<map.size()&&ty>=0&&ty<map[tx].size())&&(!map[tx][ty])&&(!visit[tx][ty])){
                visit[tx][ty]=1;
                path.emplace_back(tx+1,ty+1,i+1);
                dfs(tx,ty);
                visit[tx][ty]=0;//回溯
                path.pop_back();
            }
        }
    }
    vector<vector<Triple>> Pathfind(){
        visit.resize(map.size(),vector<int>(map[0].size(),0));//0表示未访问 1表示已访问
        visit[startx-1][starty-1]=1;
        path.emplace_back(startx,starty,1);
        dfs(startx-1,starty-1);
        return path_sum;
    }
};
int main()
{
    int m,n,startx,starty,endx,endy;
    cin>>m>>n>>startx>>starty>>endx>>endy;

    vector<vector<int>> map(m,vector<int>(n,0));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>map[i][j];
        }
    }

    PathFinder pf(map);
    pf.input(startx,starty,endx,endy);
    vector<vector<Triple>> path_sum=pf.Pathfind();

    int count=path_sum.size();
    int i,j;
    if(count==0) cout<<"no";
    for(i=0;i<count;i++){
        cout<<"第"<<i+1<<"条路经"<<":";
        j=0;
        for(j=0;j<path_sum[i].size();j++){
            if(j<path_sum[i].size()-1){
                cout<<"("<<get<0>(path_sum[i][j])<<","<<get<1>(path_sum[i][j])
                    <<","<<get<2>(path_sum[i][j+1])<<")"<<",";
                continue;
            }
            cout<<"("<<get<0>(path_sum[i][j])<<","<<get<1>(path_sum[i][j])
                <<","<<"1"<<")";
        }
        cout<<endl;
    }
    return 0;
}