题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
问题描述
解体思路
此题我的思路是从出发点开始，每个点都有四个方向可以走，分别是上下左右，对上下左右四个点分别进行判断，如果可行，则将其加入路径数组中。从 （0，0）出发即可。
我们只需要保存路径数组与对于该路径使用过的点，判断上下左右四个方向是否可行需要检查下面几个条件：
// 1 先检查是否超出地图边界
// 2 检查是否为走过的点
// 3 检查是否为墙壁
// 4 以上都可行则探索该点，否则表示其不可以走了，不做处理
对于不是出口点且已经无路可走的路径，我们直接放弃即可。
如果已经到了出口点，将递归得到的该路径保存于一个全局变量中即可。
详细代码与注释
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 保存第一行输入的矩阵信息
let info;
// 地图数组
let map = [];
// 保存所有可抵达终点的路径
let directions = [];
void async function () {
// Write your code here
// 读取第一行信息
info = await readline();
// 以空格分割开，转化为字符串数组
info = info.split(' ');
// 将数组的每个元素转化为数字
info = info.map(item=>{
return parseInt(item);
});
// 与info同理，因为第一个数字代表矩阵行数，则这里使用info[0]获取地图矩阵需要读取几次
for(let i = 0; i < info[0]; i++) {
let line = await readline();
line = line.split(' ');
line = line.map(item=>{
return parseInt(item);
});
map.push(line);
}
// 递归函数
findWayOut([[0,0]], new Set(['0,0']));
// 递归完成后，directions数组保存了所有路径，这里获取了最短的那条路径
let minLength = directions[0].length;
let minPlace = 0;
for(let i = 1; i < directions.length; i++) {
if(directions[i].length < minLength) {
minLength = directions[i].length;
minPlace = i;
}
}
let minArr = directions[minPlace];
// 遍历输出最短的路径
for(let i = 0; i < minArr.length; i++) {
console.log('(' + minArr[i][0] + ',' + minArr[i][1] + ')');
}
}()
// 递归函数，
// 其中direction保存一个数组，数组存储的信息是到某点所有经过的点，注意direction的最后一个元素
// hadpassed为一个Set类型的实例，保存着已经经过的点
function findWayOut(direction, hadPassed) {
// direction的最后一个元素代表该路径的最后一个点，我们根据此点继续向后寻找路线
let positionNow = direction[direction.length - 1];
// 判断是否为出口点
if (positionNow[0] == map.length-1 && positionNow[1] == map[0].length-1) {
// 如果为出口点则当前direction已经完成一条路径
directions.push(direction);
return true;
}
// 非出口点，则需要继续往下找路径
else {
// 接下来可以往四个方向走，上下左右四个点，对每个点进行如下检查
// 1 先检查是否超出地图边界
// 2 检查是否为走过的点
// 3 检查是否为墙壁
// 4 以上都可行则探索上方那个点，否则表示上方不可以走了，不做处理
let up = [(positionNow[0] - 1), (positionNow[1])];
let down = [(positionNow[0] + 1), (positionNow[1])];
let left = [(positionNow[0]), (positionNow[1] - 1)];
let right = [(positionNow[0]), (positionNow[1] + 1)];
// ways变量用于标记是否为死点
// 如果非出口点，且上下左右都不能再走，则为死点，此时ways为0；
let ways = 0;
// up点
// 其中chargeOutOfMap、chargeHavePassed、chargeIsWall的作用如其字面意义
// 具体代码及注释见代码末尾处
if (chargeOutOfMap(up)) {
// 超出，不处理
}
else {
if (chargeHavePassed(up, hadPassed)) {
// 经过，不处理
}
else {
if (chargeIsWall(up)) {
// 是墙， 不处理
}
else {
// 可以前往up点
// 此时我们需要将up点放入一个新的Set对象中，记录该点对于该路线已经走过
let passed = '' + up[0] + ',' + up[1];
let newHadPassed = new Set(hadPassed);
newHadPassed.add(passed);
// 同时ways+=1，代表direction最后一个点并非死点
ways++;
// 获取direction的一个copy：newDirection，并将up点放入
// 下次直接对newDirection进行下一步寻找
let newDirection = [...direction];
newDirection.push(up);
// 下一步寻找
findWayOut(newDirection, newHadPassed);
}
}
}
// 其他方向同理
// down
if (chargeOutOfMap(down)) {
// 超出，不处理
}
else {
if (chargeHavePassed(down, hadPassed)) {
// 经过，不处理
}
else {
if (chargeIsWall(down)) {
// 是墙， 不处理
}
else {
// 可以前往up点
let passed = '' + down[0] + ',' + down[1];
let newHadPassed = new Set(hadPassed);
newHadPassed.add(passed);
ways++;
let newDirection = [...direction];
newDirection.push(down);
findWayOut(newDirection, newHadPassed);
}
}
}
// left
if (chargeOutOfMap(left)) {
// 超出，不处理
}
else {
if (chargeHavePassed(left, hadPassed)) {
// 经过，不处理
}
else {
if (chargeIsWall(left)) {
// 是墙， 不处理
}
else {
// 可以前往up点
let passed = '' + left[0] + ',' + left[1];
let newHadPassed = new Set(hadPassed);
newHadPassed.add(passed);
ways++;
let newDirection = [...direction];
newDirection.push(left);
findWayOut(newDirection, newHadPassed);
}
}
}
// right
if (chargeOutOfMap(right)) {
// 超出，不处理
}
else {
if (chargeHavePassed(right, hadPassed)) {
// 经过，不处理
}
else {
if (chargeIsWall(right)) {
// 是墙， 不处理
}
else {
// 可以前往up点
let passed = '' + right[0] + ',' + right[1];
let newHadPassed = new Set(hadPassed);
newHadPassed.add(passed);
ways++;
let newDirection = [...direction];
newDirection.push(right);
findWayOut(newDirection, newHadPassed);
}
}
}
// 如果为死点，return false，其实这里无关紧要
if (ways == 0) {
return false;
}
}
}
// 如果position超出边界返回true
function chargeOutOfMap(position) {
if(position[0]<0 || position[0] >= info[0] || position[1]<0 || position[1]>=info[1]) {
return true;
}
else {
return false;
}
}
// 如果position之前经过了，返回true
function chargeHavePassed(position,hadPassed) {
let passed = hadPassed.has('' + position[0] + ',' +position[1]);
return passed;
}
// 如果position点为墙，则返回true
function chargeIsWall(position) {
if(map[position[0]][position[1]] == 1) {
return true;
}
else {
return false;
}
}
此解法可以用于多解。
后续优化思路
1 如果某个路径的长度为矩阵的长+宽-1，那么他毫无疑问是最短路径，则后续可以不用寻找了，除非题目要求求出所有最短路径。
2 针对本题因为题目说有且只有一个可以到达终点的路径，如果求出一个解其实就已经结束了。
3 为了方便理解，我的代码的findWayOut用了两个参数，可以发现direction参数与hadPassed参数保存的数据其实是对应的，完全不需要再使用一个hadPassed变量，直接将direction数组转化为字符串数组并使用indexOf()函数判断是否存在。
let a = [[1,2],[2,5]];
let b = a.map(item=>{return ''+item[0] + ',' + item[1]}); // // ['1,2', '2,5']
if( b.indexOf('2,5') != -1 ){
// 此时说明已经经过 （2，5）这个点
}
4 为了方便查看，对于上下左右四个点我并没有写为函数然后复用，实际应该复用，更为整洁。
查看7道真题和解析