c语言迷宫多条路径求解

Question

【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。

找到迷宫从起点到终点的所有路径，输出路径条数。如果从起点到终点没有路径，则输出NO PASS!
注：所有迷宫的起点为左上角，终点为右下角。
【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。



Answer 1

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
//信息太少，先假设迷宫最多100层
const int SIZE = 100;
string  mg[SIZE];
int book[SIZE][SIZE] = { 0 };
int v[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

void dfs(int m,int n,vector<char>& road,int i,int j, vector<vector<char>> &ans)
{
    //到达终点
    if (i == m && j == n)
    {
        ans.push_back(road);
    }
    else
    {
        for (int k = 0; k < 4; k++)
        {
            //上下左右走，并标记走过的位置
            int vi = i + v[k][0];
            int vj = j + v[k][1];
            if (vi >= 0 && vi <= m && vj >= 0 && vj <= n && book[vi][vj] == 0&&mg[vi][vj]=='0')
            {
                switch (k)
                {
                case 0:road.push_back('R'); break;
                case 1:road.push_back('L'); break;
                case 2:road.push_back('D'); break;
                case 3:road.push_back('U'); break;
                default:
                    break;
                }
                book[vi][vj] = 1;
                dfs(m, n, road, vi, vj, ans);
                //回溯
                book[vi][vj] = 0;
                road.pop_back();
            }
        }
    }
    
}
int main()
{
    //读入地图
    int i;
    for (i = 0; i < SIZE; i++)
    {
        string temp;
        getline(cin, temp);
        if (temp.empty())
        {
            break;
        }
        mg[i] = temp;
    }
    vector<char> road;
    vector<vector<char>> ans;
    dfs(i-1, mg[0].length()-1, road, 0, 0,ans);
    if (ans.size())
    {
        cout << ans.size() << endl;
    }
    else
    {
        cout << "NO PASS!" << endl;
        return 0;
    }
    
    for (int i = 0; i < (int)ans.size(); i++)
    {
        for (int j = 0; j < (int)ans[i].size(); j++)
        {
            cout << ans[i][j];
        }
        cout << endl;
    }
}