problem

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

 

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

 

Constraints:

  • 1 <= m, n <= 105
  • 2 <= m * n <= 105
  • 1 <= guards.length, walls.length <= 5 * 104
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= rowi, rowj < m
  • 0 <= coli, colj < n
  • All the positions in guards and walls are unique.

submission

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Cell {
    Wall,
    Guard,
    Unguarded,
    Guarded,
}

// boring problem, just mark and count
impl Solution {
    pub fn count_unguarded(
        m: i32,
        n: i32,
        guards: Vec<Vec<i32>>,
        walls: Vec<Vec<i32>>,
    ) -> i32 {
        let in_grid = |row: i32, col: i32| {
            0 <= row && row < m && 0 <= col && col < n
        };
        fn is_solid(cell: Cell) -> bool {
            cell == Cell::Guard || cell == Cell::Wall
        }
        let mut grid = vec![vec![Cell::Unguarded; n as usize]; m as usize];
        for wall in &walls {
            let (row, col) = (wall[0] as usize, wall[1] as usize);
            grid[row][col] = Cell::Wall;
        }
        for guard in &guards {
            let (row, col) = (guard[0] as usize, guard[1] as usize);
            grid[row][col] = Cell::Guard;
        }
        for guard in &guards {
            for [dy, dx] in [[0, 1], [-1, 0], [1, 0], [0, -1]] {
                let (mut row, mut col) = (guard[0] + dy, guard[1] + dx);
                while in_grid(row, col)
                    && !is_solid(grid[row as usize][col as usize])
                {
                    grid[row as usize][col as usize] = Cell::Guarded;
                    row += dy;
                    col += dx;
                }
            }
        }
        grid.into_iter()
            .flat_map(|row| row.into_iter())
            .filter(|&cell| cell == Cell::Unguarded)
            .count() as _
    }
}