commit 3a9f4581c48f2bc100cce8630201e23ab5f14365
parent bd300c28ba61b8e9c6c003255a65d4a8e685fdb9
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 22 Nov 2024 00:41:19 +0100
Add problem 2257
Diffstat:
2 files changed, 129 insertions(+), 0 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -36,6 +36,10 @@ name = "2601"
path = "src/bin/2601-prime-subtraction-operation.rs"
[[bin]]
+name = "2257"
+path = "src/bin/2257-count-unguarded-cells-in-the-grid.rs"
+
+[[bin]]
name = "19"
path = "src/bin/0019-remove-nth-node-from-end-of-list.rs"
diff --git a/src/bin/2257-count-unguarded-cells-in-the-grid.rs b/src/bin/2257-count-unguarded-cells-in-the-grid.rs
@@ -0,0 +1,125 @@
+/// 2257. Count Unguarded Cells in the Grid (Medium)
+///
+/// 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*.
+///
+
+use leetcode::*;
+
+#[derive(Default, Clone, Copy, PartialEq, Eq)]
+enum State {
+ #[default]
+ Empty,
+ Guard,
+ Wall,
+ Counted
+}
+
+struct Solution {}
+
+impl Solution {
+ pub fn count_unguarded(m: i32, n: i32, guards: Vec<Vec<i32>>, walls: Vec<Vec<i32>>) -> i32 {
+ let (n, m) = (n as usize, m as usize);
+ let (w, g) = (walls.len(), guards.len());
+ let mut map = vec![vec![State::Empty; n]; m];
+ for w in walls {
+ let (y, x) = (w[0] as usize, w[1] as usize);
+ map[y][x] = State::Wall;
+ }
+ for g in guards {
+ let (y, x) = (g[0] as usize, g[1] as usize);
+ map[y][x] = State::Guard;
+ }
+ let mut sum = 0;
+ for row in map.iter_mut() {
+ let mut guard = false;
+ let mut start = 0;
+ for x in 0..=n {
+ if x == n && guard || x < m && (row[x] == State::Guard || guard) {
+ for v in row.iter_mut().take(x).skip(start) {
+ if *v != State::Counted {
+ sum += 1;
+ *v = State::Counted;
+ }
+ }
+ }
+ if x < n && (row[x] == State::Guard || row[x] == State::Wall) {
+ start = x + 1;
+ guard = row[x] == State::Guard;
+ }
+ }
+ }
+ for x in 0..n {
+ let mut guard = false;
+ let mut start = 0;
+ for y in 0..=m {
+ if y == m && guard || y < m && (map[y][x] == State::Guard || guard) {
+ for v in map.iter_mut().take(y).skip(start) {
+ if v[x] != State::Counted {
+ sum += 1;
+ v[x] = State::Counted;
+ }
+ }
+ }
+ if y < m && (map[y][x] == State::Guard || map[y][x] == State::Wall) {
+ start = y + 1;
+ guard = map[y][x] == State::Guard;
+ }
+ }
+ }
+ (n * m - w - g - sum) as i32
+ }
+}
+
+pub fn main() {
+ let guards = arg(3).split("|").map(leetcode::parse).collect();
+ let walls = arg(4).split("|").map(leetcode::parse).collect();
+ println!("{}", Solution::count_unguarded(arg_into(1), arg_into(2), guards, walls));
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::Solution;
+
+ #[test]
+ fn test() {
+ 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);
+ 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);
+ }
+}
