游戏

前言 继续来闯关，第二小问还卡了我挺长时间，少了一个小判断。。。 题目 ....#..... ....+---+# ....|...|. ..#.|...|. ....|..#|. ....|...|. .#.O^---+. ........#. #......... ......#... 这一问是要在地图上放置障碍物，使得守卫进入循环，避免发现我们，比如下面在(6,3)处放置一个障碍物，就会导致守卫循环得走一条路，需要我们找出有多少个位置放上障碍物会导致守卫进入循环。 思路 以前还真没有做过如何判断矩阵中循环路径，一开始没什么思路，后面想到，守卫走过的步数是小于整个矩阵的大小的，如果守卫走的步数巨大，那不就说明守卫进入了循环吗？ 根据这个思路我们很快就可以改好第一版代码 解法 我们只需在 while循环中加一个变量来记录守卫走过的步数，当超过一定的数值就退出循环，我这里设置的是矩阵大小的 10 倍。 function checked(matrix, oi, oj) { const rows = matrix.length; const cols = matrix[0].length; let i = oi; let j = oj; let pos = 'up'; let step = 0; while (i < rows && i >= 0 && j < cols && j >= 0) { step++; if (step > cols * rows * 10) { return 1; } if (pos === 'up') { if (matrix[i - 1] && matrix[i - 1][j] === '#') { j++; pos = transformPosMap[pos]; } else { i--; } } else if (pos === 'right') { if (matrix[i][j + 1] === '#') { i++; pos = transformPosMap[pos]; } else { j++; } } else if (pos === 'down') { if (matrix[i + 1] && matrix[i + 1][j] === '#') { j--; pos = transformPosMap[pos]; } else { i++; } } else if (pos === 'left') { if (matrix[i][j - 1] === '#') { i--; pos = transformPosMap[pos]; } else { j--; } } } return 0; } 其实我们只需要在守卫走过的路径上放障碍物，可以节省一些判断，因为在守卫没走过的地方放障碍物不会影响到守卫的路径。...

前言 代码的出现 已经过到第六天啦，这关逐渐有意思起来了，这里记录一下我的解法，当然不是最优的解法，第一时间能想到的且最笨的解法。 守卫加里凡特 这天的名字叫 Guard Gallivant，要算出守卫在地图中走过的面积，地图如下： ....#..... .........# .......... ..#....... .......#.. .......... .#..^..... ........#. #......... ......#... 守卫一开始是朝着箭头的方向开始走，只要遇到 # 就往顺时针旋转 90° 的方向继续走，直到走出地图。 解题 矩阵里查找线路，我们很容易想到可以使用深度优先遍历，而且递归的写法更清晰明了，所以一开始我就决定用递归深度优先来解。 当遇到 # 就顺时针旋转 90°，我们可以先定义一个字典来存一下，遇到 # 要转变的下一个方向 const transformPosMap = { 'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up' } 然后我们开始定义递归函数 dfs，我们用一个 visited 数组来记录守卫走过的路，走过的置为 1，最后我们计算一下 visited 里的 1 的数量就得出这题的答案。 const dfs = (i, j, visited, matrix, rows, cols, pos) => { if (i >= rows || i < 0 || j >= cols || j < 0) return; if (visited[i][j] === 0) { visited[i][j] = 1; }; if (pos === 'up') { if (matrix[i - 1] && matrix[i - 1][j] === '#') { return dfs(i, j + 1, visited, matrix, rows, cols, transformPosMap[pos]); } else { return dfs(i - 1, j, visited, matrix, rows, cols, pos); } } else if (pos === 'right') { if (matrix[i][j + 1] === '#') { return dfs(i + 1, j, visited, matrix, rows, cols, transformPosMap[pos]); } else { return dfs(i, j + 1, visited, matrix, rows, cols, pos); } } else if (pos === 'down') { if (matrix[i + 1] && matrix[i + 1][j] === '#') { return dfs(i, j - 1, visited, matrix, rows, cols, transformPosMap[pos]); } else { return dfs(i + 1, j, visited, matrix, rows, cols, pos); } } else if (pos === 'left') { if (matrix[i][j - 1] === '#') { return dfs(i - 1, j, visited, matrix, rows, cols, transformPosMap[pos]); } else { return dfs(i, j - 1, visited, matrix, rows, cols, pos); } } } dfs 函数写出来就简单了，我们先找到入口坐标, 记在变量 oi，oj 上，然后调用 dfs 函数，最后遍历 visited 二维数组里 1 的数量就大功告成啦...