1568. Minimum Number of Days to Disconnect Island Hard

1/**
2 * [1568] Minimum Number of Days to Disconnect Island
3 *
4 * You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's.
5 * The grid is said to be connected if we have exactly one island, otherwise is said disconnected.
6 * In one day, we are allowed to change any single land cell (1) into a water cell (0).
7 * Return the minimum number of days to disconnect the grid.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land1.jpg" style="width: 500px; height: 169px;" />
11 * Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
12 * Output: 2
13 * Explanation: We need at least 2 days to get a disconnected grid.
14 * Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land2.jpg" style="width: 404px; height: 85px;" />
18 * Input: grid = [[1,1]]
19 * Output: 2
20 * Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	m == grid.length
26 * 	n == grid[i].length
27 * 	1 <= m, n <= 30
28 * 	grid[i][j] is either 0 or 1.
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/
34// discuss: https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn min_days(grid: Vec<Vec<i32>>) -> i32 {
40        0
41    }
42}
43
44// submission codes end
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test_1568() {
52    }
53}
54