2257. Count Unguarded Cells in the Grid

Leetcode link

题目简介

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} guards
 * @param {number[][]} walls
 * @return {number}
 */

本题给了我们一个 m*n 的格子，并且在格子上标注了 guards 跟 walls 分别代表守卫跟墙体

每个守卫可以看到上下左右四个方向的所有格子，除非遇到了墙体或者另一个守卫

题目要求我们返回在给定的守卫以及墙体的情况下，有多少个格子没有被守卫看到

解题思路

很遗憾，这题其实只有一个模拟的解法

我们可以把格子分成三类：

1. 没被守卫看到的格子
2. 守卫或墙体在的格子
3. 能被守卫看到的格子

我们模拟的方法就是根据题目给定的第二类格子，推导出第三类格子，最后计算第一类格子的数量

模拟步骤如下：

1. 用一个 m*n 的数组模拟所有格子
2. 根据题目参数标注守卫以及墙体的位置到数组对应的格子上
3. 遍历所有守卫，对守卫的四个方向持续遍历，直到遇到了另一个守卫或者墙体，遍历过程中遇到的格子全部标注成 “能被守卫看到的格子”
4. 当第三步遍历完成后，遍历整个数组找出 “没被守卫看到的格子” 的个数返回

Javascript

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} guards
 * @param {number[][]} walls
 * @return {number}
 */
var countUnguarded = function (m, n, guards, walls) {
    const UNGARDED_AREA = 0
    const GUARDED_AREA = 1
    const WALL_AND_GUARD_AREA = 2
    const arr = new Array(m).fill(0).map(item => new Array(n).fill(UNGARDED_AREA))

    for (const [row, col] of walls) {
        arr[row][col] = WALL_AND_GUARD_AREA
    }

    for (const [row, col] of guards) {
        arr[row][col] = WALL_AND_GUARD_AREA
    }

    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    for (const [row, col] of guards) {
        for (const dir of dirs) {
            let newRow = row + dir[0]
            let newCol = col + dir[1]
            while(newRow >=0 && newCol >=0 && newRow < m && newCol < n && arr[newRow][newCol] !== WALL_AND_GUARD_AREA) {
                arr[newRow][newCol] = GUARDED_AREA
                newRow += dir[0]
                newCol += dir[1]
            }
        }
    }

    const res = arr.reduce((acc, cur) => {
        return cur.filter(item => item === UNGARDED_AREA).length + acc
    }, 0)
    return res
};