827. Making A Large Island Hard

1/**
2 * [827] Making A Large Island
3 *
4 * You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
5 * 
6 * Return the size of the largest island in grid after applying this operation.
7 * 
8 * An island is a 4-directionally connected group of 1s.
9 * 
10 *  
11 * Example 1:
12 * 
13 * 
14 * Input: grid = [[1,0],[0,1]]
15 * Output: 3
16 * Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
17 * 
18 * 
19 * Example 2:
20 * 
21 * 
22 * Input: grid = [[1,1],[1,0]]
23 * Output: 4
24 * Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
25 * 
26 * Example 3:
27 * 
28 * 
29 * Input: grid = [[1,1],[1,1]]
30 * Output: 4
31 * Explanation: Can't change any 0 to 1, only one island with area = 4.
32 * 
33 * 
34 *  
35 * Constraints:
36 * 
37 * 
38 * 	n == grid.length
39 * 	n == grid[i].length
40 * 	1 <= n <= 500
41 * 	grid[i][j] is either 0 or 1.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/making-a-large-island/
47// discuss: https://leetcode.com/problems/making-a-large-island/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn largest_island(grid: Vec<Vec<i32>>) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_827() {
65    }
66}
67