【日常刷题】迷宫问题

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

输入描述

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述

左上角到右下角的最短路径，格式如样例所示。

分析

这道题我们将要使用动态规划中的回溯的思想,因为我们不能保证走了一步之后,接下来的后几步仍然能走得通,所以我们最好使用递归,然后判断条件是否回溯.

代码

#include <iostream>
#include <vector>
using namespace std;
int ROW;
int COL;
vector<vector<int>> maze;
vector<vector<int>> path_tmp;
vector<vector<int>> path_best;void getbestpath(int i,int j)
{maze[i][j] = 1;path_tmp.push_back({i,j});//如果找到了出口if(i == ROW - 1 && j == COL - 1){//将临时路径和最佳路径进行比较if(path_best.empty() || path_best.size() > path_tmp.size()){//储存最佳路径path_best = path_tmp;}}//如果没有找到出口//向上查找if(i - 1 >= 0 && maze[i-1][j] == 0){getbestpath(i-1,j);}//向下查找if(i + 1 < ROW && maze[i+1][j] == 0){getbestpath(i+1,j);}//向左查找if(j - 1 >= 0 && maze[i][j-1] == 0){getbestpath(i,j-1);}//向右查找if(j + 1 < COL && maze[i][j+1] == 0){getbestpath(i,j+1);}//全部不可走->回溯maze[i][j] = 0;//开放该路径path_tmp.pop_back();
}int main() {while(cin >> ROW >> COL){maze = vector<vector<int>>(ROW,vector<int>(COL,0));// 定义迷宫for(int i = 0; i < ROW; i++)//输入迷宫{for(int j = 0; j < COL ; j++){cin >> maze[i][j];}}getbestpath(0,0);//从（0，0）开始走//打印结果for(int i = 0; i < path_best.size(); i++){cout << "(" << path_best[i][0] << "," << path_best[i][1] << ")" << endl;}}
}