Depth-First Search
Breadth-First Search
Array
Matrix
Strongly Connected Component
Description
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.
The grid is said to be connected if we have exactly one island , otherwise is said disconnected .
In one day, we are allowed to change any single land cell (1)
into a water cell (0)
.
Return the minimum number of days to disconnect the grid .
Example 1:
Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
Example 2:
Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j]
is either 0
or 1
.
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 class Solution :
def minDays ( self , grid : List [ List [ int ]]) -> int :
if self . count ( grid ) != 1 :
return 0
m , n = len ( grid ), len ( grid [ 0 ])
for i in range ( m ):
for j in range ( n ):
if grid [ i ][ j ] == 1 :
grid [ i ][ j ] = 0
if self . count ( grid ) != 1 :
return 1
grid [ i ][ j ] = 1
return 2
def count ( self , grid ):
def dfs ( i , j ):
grid [ i ][ j ] = 2
for a , b in [[ 0 , - 1 ], [ 0 , 1 ], [ 1 , 0 ], [ - 1 , 0 ]]:
x , y = i + a , j + b
if 0 <= x < m and 0 <= y < n and grid [ x ][ y ] == 1 :
dfs ( x , y )
m , n = len ( grid ), len ( grid [ 0 ])
cnt = 0
for i in range ( m ):
for j in range ( n ):
if grid [ i ][ j ] == 1 :
dfs ( i , j )
cnt += 1
for i in range ( m ):
for j in range ( n ):
if grid [ i ][ j ] == 2 :
grid [ i ][ j ] = 1
return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 class Solution {
private static final int [] DIRS = new int [] { - 1 , 0 , 1 , 0 , - 1 };
private int [][] grid ;
private int m ;
private int n ;
public int minDays ( int [][] grid ) {
this . grid = grid ;
m = grid . length ;
n = grid [ 0 ] . length ;
if ( count () != 1 ) {
return 0 ;
}
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 1 ) {
grid [ i ][ j ] = 0 ;
if ( count () != 1 ) {
return 1 ;
}
grid [ i ][ j ] = 1 ;
}
}
}
return 2 ;
}
private int count () {
int cnt = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 1 ) {
dfs ( i , j );
++ cnt ;
}
}
}
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 2 ) {
grid [ i ][ j ] = 1 ;
}
}
}
return cnt ;
}
private void dfs ( int i , int j ) {
grid [ i ][ j ] = 2 ;
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + DIRS [ k ] , y = j + DIRS [ k + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == 1 ) {
dfs ( x , y );
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 class Solution {
public :
const vector < int > dirs = { -1 , 0 , 1 , 0 , -1 };
int m , n ;
int minDays ( vector < vector < int >>& grid ) {
m = grid . size (), n = grid [ 0 ]. size ();
if ( count ( grid ) != 1 ) {
return 0 ;
}
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 1 ) {
grid [ i ][ j ] = 0 ;
if ( count ( grid ) != 1 ) {
return 1 ;
}
grid [ i ][ j ] = 1 ;
}
}
}
return 2 ;
}
int count ( vector < vector < int >>& grid ) {
int cnt = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 1 ) {
dfs ( i , j , grid );
++ cnt ;
}
}
}
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == 2 ) {
grid [ i ][ j ] = 1 ;
}
}
}
return cnt ;
}
void dfs ( int i , int j , vector < vector < int >>& grid ) {
grid [ i ][ j ] = 2 ;
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ], y = j + dirs [ k + 1 ];
if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == 1 ) {
dfs ( x , y , grid );
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 func minDays ( grid [][] int ) int {
m , n := len ( grid ), len ( grid [ 0 ])
dirs := [] int { - 1 , 0 , 1 , 0 , - 1 }
var dfs func ( i , j int )
dfs = func ( i , j int ) {
grid [ i ][ j ] = 2
for k := 0 ; k < 4 ; k ++ {
x , y := i + dirs [ k ], j + dirs [ k + 1 ]
if x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == 1 {
dfs ( x , y )
}
}
}
count := func () int {
cnt := 0
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == 1 {
dfs ( i , j )
cnt ++
}
}
}
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == 2 {
grid [ i ][ j ] = 1
}
}
}
return cnt
}
if count () != 1 {
return 0
}
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == 1 {
grid [ i ][ j ] = 0
if count () != 1 {
return 1
}
grid [ i ][ j ] = 1
}
}
}
return 2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 function minDays ( grid : number [][]) : number {
const [ m , n ] = [ grid . length , grid [ 0 ]. length ];
const dfs = ( i : number , j : number ) => {
if ( i < 0 || m <= i || j < 0 || n <= j || [ 0 , 2 ]. includes ( grid [ i ][ j ])) return ;
grid [ i ][ j ] = 2 ;
const dir = [ - 1 , 0 , 1 , 0 , - 1 ];
for ( let k = 0 ; k < 4 ; k ++ ) {
const [ y , x ] = [ i + dir [ k ], j + dir [ k + 1 ]];
dfs ( y , x );
}
};
const count = () => {
let c = 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( grid [ i ][ j ] === 1 ) {
dfs ( i , j );
c ++ ;
}
}
}
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( grid [ i ][ j ] === 2 ) {
grid [ i ][ j ] = 1 ;
}
}
}
return c ;
};
if ( count () !== 1 ) return 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( grid [ i ][ j ] === 1 ) {
grid [ i ][ j ] = 0 ;
if ( count () !== 1 ) return 1 ;
grid [ i ][ j ] = 1 ;
}
}
}
return 2 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 /**
* @param {number[][]} grid
* @return {number}
*/
var minDays = function ( grid ) {
const dirs = [ - 1 , 0 , 1 , 0 , - 1 ];
const [ m , n ] = [ grid . length , grid [ 0 ]. length ];
const dfs = ( i , j , visited ) => {
if ( i < 0 || m <= i || j < 0 || n <= j || grid [ i ][ j ] === 0 || visited [ i ][ j ]) {
return ;
}
visited [ i ][ j ] = true ;
for ( let d = 0 ; d < 4 ; d ++ ) {
const [ y , x ] = [ i + dirs [ d ], j + dirs [ d + 1 ]];
dfs ( y , x , visited );
}
};
const count = () => {
const vis = Array . from ({ length : m }, () => Array ( n ). fill ( false ));
let c = 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( grid [ i ][ j ] === 1 && ! vis [ i ][ j ]) {
c ++ ;
dfs ( i , j , vis );
}
}
}
return c ;
};
if ( count () !== 1 ) return 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( grid [ i ][ j ] === 1 ) {
grid [ i ][ j ] = 0 ;
if ( count () !== 1 ) return 1 ;
grid [ i ][ j ] = 1 ;
}
}
}
return 2 ;
};