题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let count = 1;
let m, n;
let data = [];
let res = '';
rl.on("line", function (line) {
if (count == 1) {
[m, n] = line.split(" ").map((s) => Number(s));
} else {
data.push(line.split(" "));
}
count++;
});
// 上一步我的状态 决定我这一步不能回到原状态，否则进入死循环 +x 表示我x方向前进 -x 表示我x后退一步 +y表示我y方向前进 -y表示我y方向后退 #表示初始位置
rl.on("close", function () {
let dfs = (i, j, state, s) => {
if (i < 0 || i >= m || j < 0 || j >= n) return false;
if (data[i][j] == "1") return false;
if (i == m - 1 && j == n - 1) {
if (res) res = (res.length > `${s} (${i},${j})`.length ? `${s} (${i},${j})`: res);
else res = `${s} (${i},${j})`
return
}
if (state !== '+x') dfs(i - 1, j, '-x', `${s} (${i},${j})`)
if (state !== '-x') dfs(i + 1, j, '+x', `${s} (${i},${j})`)
if (state !== '-y') dfs(i, j + 1, '+y', `${s} (${i},${j})`)
if (state !== '+y') dfs(i, j - 1, '-y', `${s} (${i},${j})`)
};
dfs(0, 0, "#", "");
if (!res) return;
res.trim().split(" ").forEach((item) => console.log(item));
});
