代码来临 2024 年第 6 天
第 1 部分
一种非常熟悉的谜题 二维网格 到处都有障碍 追踪路径 计算访问过的独特图块让我们开始吧！
一次一步解析网格：
1
2
let grid = input.split(
).map(el => el.split())
识别守卫的起始位置并将其替换为空图块：
1
2
3
4
5
6
7
8
9
let guard = null;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] == "^") {
guard = [r, c];
grid[r][c] = ".";
}
}
}
创建一个对象来跟踪守卫当前的旋转：
1
2
3
4
5
6
let facing = [
[-1,0],
[0,1],
[1,0],
[0,-1]
]
跟踪访问的单元格：
1
let visited = new set()
每次移动时，我都会尝试将字符串化坐标添加到此 set() 中。
移动守卫：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
while (true) {
visited.add(guard.join(","));
let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
if (
next[0] >= 0 &&
next[0] < grid.length &&
next[1] >= 0 &&
next[1] < grid[0].length
) {
if (grid[next[0]][next[1]] == ".") {
guard = next;
console.log(guard);
} else if (grid[next[0]][next[1]] == "#") {
let olddirection = facing.shift();
facing.push(olddirection);
}
} else {
break;
}
}
解释：
1
2
3
4
5
6
7
8
9
10
keep going until manually broken out of
add the current coordinate to the tracked list
record the next location to visit
if it is within the grid
if it is empty cell
move the guard
else if it is an obstacle
rotate the guard
else
break out of the loop
该算法成功为示例输入生成了 41 个已访问单元格列表！
它会为我的拼图输入生成正确的答案吗？
是的！！！
进入第二部分！
第2部分
我有点预见到了这一点，并且很害怕它老兄，检查每个可能的选项以获得一个有效的谜题。
阅读时我最大的问题是：
如何识别守卫何时进入循环？但我想我知道：
我会追踪朝向以及坐标 如果列表包含下一个添加的副本，则循环即将开始是时候让事情变得更加复杂了！
循环遍历每个单元格以找到所有循环首先，我想生成一个包含 . 的所有单元格的列表，不包括守卫的起始单元格：
1
2
3
4
5
6
7
8
9
10
11
12
let empties = [];
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] == ".") {
empties.push([r, c]);
}
if (grid[r][c] == "^") {
guard = [r, c];
grid[r][c] = ".";
}
}
}
然后，使用reduce 来迭代每个 .在网格中，复制网格和原始防护位置，在reduce内移动大量原始代码，扩展while循环以包含具有当前状态实例的跟踪坐标和旋转列表的条件：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
let part2 = empties.reduce((count, coord) => {
let guardCopy = guard.slice()
let gridCopy = grid.map(row => row.slice())
gridCopy[coord[0]][coord[1]] = "#"
let facing = [
[-1,0],
[0,1],
[1,0],
[0,-1]
]
let visited = new Set()
while (true) {
let stamp = guardCopy.join(,) + facing[0].join(,)
if (visited.has(stamp)) {
count++
break;
} else {
visited.add(stamp);
let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
if (
next[0] >= 0 &&
next[0] < gridCopy.length &&
next[1] >= 0 &&
next[1] < gridCopy[0].length
) {
if (gridCopy[next[0]][next[1]] == ".") {
guardCopy = next;
} else if (gridCopy[next[0]][next[1]] == "#") {
let oldDirection = facing.shift();
facing.push(oldDirection);
}
} else {
break;
}
}
}
return count
}, 0)
很多。
但是它有效！至少在示例输入上。
它对我有用吗？？？
嗯...运行了 30 秒。
但是...它产生了答案！
这是...
正确答案!!!
呜呼！！！
第 1 部分很容易。第 2 部分是一个艰难但受欢迎的规模提升。
袋子里还有两颗金星！
进入第 7 天。
以上就是加里凡特卫兵的详细内容，更多请关注php中文网其它相关文章！