题解 | #迷宫问题#

问题描述

解体思路

此题我的思路是从出发点开始，每个点都有四个方向可以走，分别是上下左右，对上下左右四个点分别进行判断，如果可行，则将其加入路径数组中。从 （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 为了方便查看，对于上下左右四个点我并没有写为函数然后复用，实际应该复用，更为整洁。