gpt4 book ai didi

javascript - 是否有一种算法可以在棋盘游戏中找到所有可能的路线?

转载 作者:行者123 更新时间:2023-12-04 03:26:17 26 4
gpt4 key购买 nike

我正在尝试编写一个 javascript 函数,用于在玩家无法沿对 Angular 线移动的棋盘(15x15 网格)上找到所有长度为 N 的可能路线。我能够想出一个非常简单的递归解决方案,但我怀疑它极度未优化。

代码如下:

search(n, u, v) {

if (n == 0 || isWall(u, v))
return;

board[v][u] = 2;

search(n - 1, u, v - 1);
search(n - 1, u + 1, v);
search(n - 1, u, v + 1);
search(n - 1, u - 1, v);

return;
}

board 是一个包含棋盘数据的二维数组。自由空间、墙壁和可达空间分别用 0、1 和 2 表示。

Here's an example of what is looks like given N=6

SampleBoard

编辑:如下所述,我试图在 N 或更少的移动中找到所有可到达的单元格。

最佳答案

就像其他人写的那样,您应该使用广度优先遍历而不是深度优先遍历。

其次,您不应重新访问已标记为值 2 的单元格,因此您继续的条件应该是当前单元格的值为 0。

我建议使用两个数组实现遍历:

function search(board, n, u, v) {
let count = 0;
let frontier = [[u, v]];

while (n-- > 0 && frontier.length) {
let newFrontier = [];
for (let [u, v] of frontier) {
if (board[v]?.[u] === 0) {
board[v][u] = 2;
count++;
newFrontier.push([u, v - 1], [u + 1, v], [u, v + 1], [u - 1, v]);
}
}
frontier = newFrontier;
}

return count;
}

let board = [
"11111111111111",
"10000000000001",
"10000000000001",
"10011100111001",
"10010000001001",
"10010000001001",
"10000000000001",
"10000000000001",
"10000000000001",
"10010000001001",
"10010000001001",
"10011100111001",
"10000000000001",
"10000000000001",
"11111111111111"
].map(row => Array.from(row, Number));

let res = search(board, 6, 2, 2);

console.log("number of cells reached: ", res);

console.log(board.map(row => row.join(" ")).join("\n"));

关于javascript - 是否有一种算法可以在棋盘游戏中找到所有可能的路线?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67522428/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com