2257. Count Unguarded Cells in the Grid Medium

1/**
2 * [2257] Count Unguarded Cells in the Grid
3 *
4 * 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 i^th guard and j^th wall respectively.
5 * 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.
6 * Return the number of unoccupied cells that are not guarded.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/10/example1drawio2.png" style="width: 300px; height: 204px;" />
10 * Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
11 * Output: 7
12 * Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
13 * There are a total of 7 unguarded cells, so we return 7.
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/10/example2drawio.png" style="width: 200px; height: 201px;" />
17 * Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
18 * Output: 4
19 * Explanation: The unguarded cells are shown in green in the above diagram.
20 * There are a total of 4 unguarded cells, so we return 4.
21 * 
22 *  
23 * Constraints:
24 * 
25 * 1 <= m, n <= 10^5
26 * 2 <= m * n <= 10^5
27 * 1 <= guards.length, walls.length <= 5 * 10^4
28 * 2 <= guards.length + walls.length <= m * n
29 * guards[i].length == walls[j].length == 2
30 * 0 <= rowi, rowj < m
31 * 0 <= coli, colj < n
32 * All the positions in guards and walls are unique.
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/count-unguarded-cells-in-the-grid/
38// discuss: https://leetcode.com/problems/count-unguarded-cells-in-the-grid/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    const DIRECTION: [(i32, i32); 4] = [(1, 0), (0, 1), (0, -1), (-1, 0)];
44    pub fn count_unguarded(m: i32, n: i32, guards: Vec<Vec<i32>>, walls: Vec<Vec<i32>>) -> i32 {
45        let mut grid = vec![vec![0_u8; n as usize]; m as usize];
46        for v in &guards {
47            grid[v[0] as usize][v[1]as usize] = 1;
48        }
49        for w in walls {
50            grid[w[0] as usize][w[1]as usize] = 2;
51        }
52
53        for p in guards {
54            Self::dfs(&mut grid, (p[0] as isize, p[1] as isize), 0);
55            Self::dfs(&mut grid, (p[0] as isize, p[1] as isize), 1);
56            Self::dfs(&mut grid, (p[0] as isize, p[1] as isize), 2);
57            Self::dfs(&mut grid, (p[0] as isize, p[1] as isize), 3);
58        }
59        
60        let mut result = 0;
61        for i in 0..grid.len() {
62            for j in 0..grid[0].len() {
63                if grid[i][j] == 0 {
64                    result += 1;
65                }
66            }
67        }
68
69        result
70    }
71
72    fn dfs(grid: &mut Vec<Vec<u8>>, current: (isize, isize), direction: usize) {
73        let mut x = current.0;
74        let mut y = current.1;
75        for _ in 0.. {
76            x = x + Self::DIRECTION[direction].0 as isize;
77            y = y + Self::DIRECTION[direction].1 as isize;
78    
79            if x >= grid.len() as isize || y >= grid[0].len() as isize || x < 0 || y < 0 {
80                return;
81            }
82    
83            if grid[x as usize][y as usize] == 2 || grid[x as usize][y as usize] == 1 {
84                return
85            }
86
87            if grid[x as usize][y as usize] == direction as u8 + 10 {
88                return
89            }
90            
91            grid[x as usize][y as usize] = direction as u8 + 10;
92        }
93        
94    }
95}
96
97// submission codes end
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_2257_1() {
105        assert_eq!(Solution::count_unguarded(3, 3, vec!(vec!(1,1)), vec!(vec!(0, 1), vec!(1, 0), vec!(2, 1), vec!(1, 2))), 4);
106        assert_eq!(Solution::count_unguarded(4, 6, vec!(vec!(0,0),vec!(1,1),vec!(2,3)), vec!(vec!(0,1),vec!(2,2),vec!(1,4))), 7);
107    }
108}
109