leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2257-count-unguarded-cells-in-the-grid.rs (4277B)

      1/// 2257. Count Unguarded Cells in the Grid (Medium)
      2///
      3/// You are given two integers m and n representing a *0-indexed* m x n grid.
      4/// You are also given two 2D integer arrays guards and walls where guards[i] =
      5/// [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith
      6/// guard and jth wall respectively.
      7///
      8/// A guard can see every cell in the four cardinal directions (north, east,
      9/// south, or west) starting from their position unless *obstructed* by a wall
     10/// or another guard. A cell is *guarded* if there is *at least* one guard that
     11/// can see it.
     12///
     13/// Return the number of unoccupied cells that are *not* *guarded*.
     14///
     15/// *Example 1:*
     16///
     17///   *Input:* m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls =
     18///   [[0,1],[2,2],[1,4]]
     19///   *Output:* 7
     20///   *Explanation:* The guarded and unguarded cells are shown in red and green
     21///   respectively in the above diagram.
     22///   There are a total of 7 unguarded cells, so we return 7.
     23///
     24/// *Example 2:*
     25///
     26///   *Input:* m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
     27///   *Output:* 4
     28///   *Explanation:* The unguarded cells are shown in green in the above diagram.
     29///   There are a total of 4 unguarded cells, so we return 4.
     30///
     31/// *Constraints:*
     32///
     33///   * 1 <= m, n <= 105
     34///   * 2 <= m * n <= 105
     35///   * 1 <= guards.length, walls.length <= 5 * 104
     36///   * 2 <= guards.length + walls.length <= m * n
     37///   * guards[i].length == walls[j].length == 2
     38///   * 0 <= rowi, rowj < m
     39///   * 0 <= coli, colj < n
     40///   * All the positions in guards and walls are *unique*.
     41///
     42use leetcode::*;
     43
     44#[derive(Default, Clone, Copy, PartialEq, Eq)]
     45enum State {
     46    #[default]
     47    Empty,
     48    Guard,
     49    Wall,
     50    Counted,
     51}
     52
     53struct Solution {}
     54
     55impl Solution {
     56    pub fn count_unguarded(m: i32, n: i32, guards: Vec<Vec<i32>>, walls: Vec<Vec<i32>>) -> i32 {
     57        let (n, m) = (n as usize, m as usize);
     58        let (w, g) = (walls.len(), guards.len());
     59        let mut map = vec![vec![State::Empty; n]; m];
     60        for w in walls {
     61            let (y, x) = (w[0] as usize, w[1] as usize);
     62            map[y][x] = State::Wall;
     63        }
     64        for g in guards {
     65            let (y, x) = (g[0] as usize, g[1] as usize);
     66            map[y][x] = State::Guard;
     67        }
     68        let mut sum = 0;
     69        for row in map.iter_mut() {
     70            let mut guard = false;
     71            let mut start = 0;
     72            for x in 0..=n {
     73                if x == n && guard || x < m && (row[x] == State::Guard || guard) {
     74                    for v in row.iter_mut().take(x).skip(start) {
     75                        if *v != State::Counted {
     76                            sum += 1;
     77                            *v = State::Counted;
     78                        }
     79                    }
     80                }
     81                if x < n && (row[x] == State::Guard || row[x] == State::Wall) {
     82                    start = x + 1;
     83                    guard = row[x] == State::Guard;
     84                }
     85            }
     86        }
     87        for x in 0..n {
     88            let mut guard = false;
     89            let mut start = 0;
     90            for y in 0..=m {
     91                if y == m && guard || y < m && (map[y][x] == State::Guard || guard) {
     92                    for v in map.iter_mut().take(y).skip(start) {
     93                        if v[x] != State::Counted {
     94                            sum += 1;
     95                            v[x] = State::Counted;
     96                        }
     97                    }
     98                }
     99                if y < m && (map[y][x] == State::Guard || map[y][x] == State::Wall) {
    100                    start = y + 1;
    101                    guard = map[y][x] == State::Guard;
    102                }
    103            }
    104        }
    105        (n * m - w - g - sum) as i32
    106    }
    107}
    108
    109pub fn main() {
    110    println!(
    111        "{}",
    112        Solution::count_unguarded(arg_into(1), arg_into(2), arg_into(3), arg_into(4))
    113    );
    114}
    115
    116#[cfg(test)]
    117mod tests {
    118    use crate::Solution;
    119    use leetcode::vvi;
    120
    121    #[test]
    122    fn test() {
    123        assert_eq!(
    124            Solution::count_unguarded(4, 6, vvi("[[0,0],[1,1],[2,3]]"), vvi("[[0,1],[2,2],[1,4]]")),
    125            7
    126        );
    127        assert_eq!(
    128            Solution::count_unguarded(3, 3, vvi("[[1,1]]"), vvi("[[0,1],[1,0],[2,1],[1,2]]")),
    129            4
    130        );
    131    }
    132}