[深搜][洛谷] P1238 走迷宫

总结大纲

• • 题目内容
  • 分析总结
  • 附录：源代码

题目内容

题目描述

  有一个 m × n m × n m×n 格的迷宫(表示有 m m m 行、 n n n 列)，其中有可走的也有不可走的，如果用 1 1 1 表示可以走， 0 0 0 表示不可以走，文件读入这 m × n m×n m×n 个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 − 1 −1 −1 表示无路）。

  优先顺序：左上右下。数据保证随机生成。

输入格式

  第一行是两个数 m , n ( 1 < m , n < 15 ) m,n(1<m,n<15) m,n(1<m,n<15)，接下来是 m m m 行 n n n 列由 1 1 1 和 0 0 0 组成的数据，最后两行是起始点和结束点。

输出格式

  所有可行的路径，描述一个点时用 ( x , y ) (x,y) (x,y) 的形式，除开始点外，其他的都要用 -> 表示方向。

  如果没有一条可行的路则输出 − 1 −1 −1。

分析总结

思路分析

  这是一道基础的迷宫问题，需要利用深度优先搜索进行解决。其基本思路如下：将移动的方向用坐标向量表示，在迷宫的每一点分别就各个方向进行遍历判断，根据判断结果进行移动，在到达下一点后则继续重复进行上述判断，直至到达终点。其中，各个方向遍历的次序会影响到输出结果的顺序，因此需要根据题目具体设定。

  深搜的思路可以表示如下：

int search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i++)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t+1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
}
// 注: 分享自洛谷 P1238 题解 @ybb756032937 

  其中，需要特别设置一个与地图相同大小的标记数组用来记录每一点是否在之前涉足过，并在每次递归结束后恢复标记之前的状态，这样最终输出的便是所有可能的路径。这里应该注意的是，如果递归后不删除标记，那么由于终点处始终带有标记，此时便只能输出第一条可能的路径，其他潜在的路径就无法输出。前者可以用于所有可能路径的枚举，后者则可以用作可通性的判断。

过程总结

  其实深度优先搜索的原理并不复杂，上述代码即可描述，只是还需要实现题目中的要求。正如枕头做起来容易，可是在上面绣花却是一件费工夫的事情。

  题目要求将所有可能的路径，按照经过的坐标进行输出。因此采用一个栈对算法的位置进行实时跟踪，一旦前进，就将彼处的坐标压栈，一旦退回，就将彼处的坐标退栈。由于 STL 中的栈无法遍历，因此将其压入额外的临时栈中进行输出，一边输出一遍压回，从而实现路径坐标的正序输出。

  此外，算法中的坐标从 0 0 0 开始，而输入输出的坐标则是从 1 1 1 开始，因此程序还在传参等过程中，对其进行了转换。

附录：源代码

#include <iostream>
#include <string.h>
#include <stack>

using namespace std;

int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int plat[15][15];
int sgn[15][15];
int row, column;
int begin_x, begin_y;
int end_x, end_y;
bool solvable = false;

stack<int> step;

void dfs(int x, int y){
    // exit condition
    if(x == end_x - 1 && y == end_y - 1){
        stack<int> temp;        // temporarily reverse the order
        while(step.empty() == false){
            temp.push(step.top());
            step.pop();
        }
        // complete data migration
        // output the result and send the data back
        while(temp.empty() == false){
            int px = temp.top();
            temp.pop();
            int py = temp.top();
            temp.pop();

            if(temp.empty() == true)
                cout << "(" << px << "," << py << ")";
            else
                cout << "(" << px << "," << py << ")->";

            step.push(px);
            step.push(py);
        }
        cout << endl;
        solvable = true;
        return;
    }

    for(int k = 0; k < 4; k++){
        // boundary judgement
        if(x + dir[k][0] < 0 || x + dir[k][0] >= row)
            continue;
        if(y + dir[k][1] < 0 || y + dir[k][1] >= column)
            continue;

        if(plat[x + dir[k][0]][y + dir[k][1]] == 1 && sgn[x + dir[k][0]][y + dir[k][1]] == 0){
            sgn[x + dir[k][0]][y + dir[k][1]] = 1;
            step.push(x + dir[k][0] + 1);
            step.push(y + dir[k][1] + 1);
            dfs(x + dir[k][0], y + dir[k][1]);
            step.pop();
            step.pop();
            sgn[x + dir[k][0]][y + dir[k][1]] = 0;
        }
    }
}

int main()
{
    cin >> row >> column;

    for(int i = 0; i < row; i++)
        for(int j = 0; j < column; j++){
            cin >> plat[i][j];
            sgn[i][j] = 0;
        }

    cin >> begin_x >> begin_y;
    cin >> end_x >> end_y;
    sgn[begin_x - 1][begin_y - 1] = 1;
    step.push(begin_x);
    step.push(begin_y);
    dfs(begin_x - 1, begin_y - 1);
    if(solvable == false)
        cout << -1;

    return 0;
}