Depth-First Search
Breadth-First Search
Union Find
Array
Hash Table
Matrix
Description
An n x n
grid is composed of 1 x 1
squares where each 1 x 1
square consists of a '/'
, '\'
, or blank space ' '
. These characters divide the square into contiguous regions.
Given the grid grid
represented as a string array, return the number of regions .
Note that backslash characters are escaped, so a '\'
is represented as '\\'
.
Example 1:
Input: grid = [" /","/ "]
Output: 2
Example 2:
Input: grid = [" /"," "]
Output: 1
Example 3:
Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
Constraints:
n == grid.length == grid[i].length
1 <= n <= 30
grid[i][j]
is either '/'
, '\'
, or ' '
.
Solutions
Solution 1: Union-Find
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
35 class Solution :
def regionsBySlashes ( self , grid : List [ str ]) -> int :
def find ( x ):
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
def union ( a , b ):
pa , pb = find ( a ), find ( b )
if pa != pb :
p [ pa ] = pb
nonlocal size
size -= 1
n = len ( grid )
size = n * n * 4
p = list ( range ( size ))
for i , row in enumerate ( grid ):
for j , v in enumerate ( row ):
k = i * n + j
if i < n - 1 :
union ( 4 * k + 2 , ( k + n ) * 4 )
if j < n - 1 :
union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 )
if v == '/' :
union ( 4 * k , 4 * k + 3 )
union ( 4 * k + 1 , 4 * k + 2 )
elif v == ' \\ ' :
union ( 4 * k , 4 * k + 1 )
union ( 4 * k + 2 , 4 * k + 3 )
else :
union ( 4 * k , 4 * k + 1 )
union ( 4 * k + 1 , 4 * k + 2 )
union ( 4 * k + 2 , 4 * k + 3 )
return size
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 {
private int [] p ;
private int size ;
public int regionsBySlashes ( String [] grid ) {
int n = grid . length ;
size = n * n * 4 ;
p = new int [ size ] ;
for ( int i = 0 ; i < p . length ; ++ i ) {
p [ i ] = i ;
}
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
int k = i * n + j ;
if ( i < n - 1 ) {
union ( 4 * k + 2 , ( k + n ) * 4 );
}
if ( j < n - 1 ) {
union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 );
}
char v = grid [ i ] . charAt ( j );
if ( v == '/' ) {
union ( 4 * k , 4 * k + 3 );
union ( 4 * k + 1 , 4 * k + 2 );
} else if ( v == '\\' ) {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 2 , 4 * k + 3 );
} else {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 1 , 4 * k + 2 );
union ( 4 * k + 2 , 4 * k + 3 );
}
}
}
return size ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
private void union ( int a , int b ) {
int pa = find ( a );
int pb = find ( b );
if ( pa == pb ) {
return ;
}
p [ pa ] = pb ;
-- size ;
}
}
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 class Solution {
public :
vector < int > p ;
int size ;
int regionsBySlashes ( vector < string >& grid ) {
int n = grid . size ();
size = n * n * 4 ;
p . resize ( size );
for ( int i = 0 ; i < size ; ++ i ) p [ i ] = i ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
int k = i * n + j ;
if ( i < n - 1 ) merge ( 4 * k + 2 , ( k + n ) * 4 );
if ( j < n - 1 ) merge ( 4 * k + 1 , ( k + 1 ) * 4 + 3 );
char v = grid [ i ][ j ];
if ( v == '/' ) {
merge ( 4 * k , 4 * k + 3 );
merge ( 4 * k + 1 , 4 * k + 2 );
} else if ( v == '\\' ) {
merge ( 4 * k , 4 * k + 1 );
merge ( 4 * k + 2 , 4 * k + 3 );
} else {
merge ( 4 * k , 4 * k + 1 );
merge ( 4 * k + 1 , 4 * k + 2 );
merge ( 4 * k + 2 , 4 * k + 3 );
}
}
}
return size ;
}
void merge ( int a , int b ) {
int pa = find ( a );
int pb = find ( b );
if ( pa == pb ) return ;
p [ pa ] = pb ;
-- size ;
}
int find ( int x ) {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
}
};
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 func regionsBySlashes ( grid [] string ) int {
n := len ( grid )
size := n * n * 4
p := make ([] int , size )
for i := range p {
p [ i ] = i
}
var find func ( x int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
union := func ( a , b int ) {
pa , pb := find ( a ), find ( b )
if pa == pb {
return
}
p [ pa ] = pb
size --
}
for i , row := range grid {
for j , v := range row {
k := i * n + j
if i < n - 1 {
union ( 4 * k + 2 , ( k + n ) * 4 )
}
if j < n - 1 {
union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 )
}
if v == '/' {
union ( 4 * k , 4 * k + 3 )
union ( 4 * k + 1 , 4 * k + 2 )
} else if v == '\\' {
union ( 4 * k , 4 * k + 1 )
union ( 4 * k + 2 , 4 * k + 3 )
} else {
union ( 4 * k , 4 * k + 1 )
union ( 4 * k + 1 , 4 * k + 2 )
union ( 4 * k + 2 , 4 * k + 3 )
}
}
}
return size
}
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 function regionsBySlashes ( grid : string []) : number {
const find = ( x : number ) => {
if ( p [ x ] !== x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
};
const union = ( a : number , b : number ) => {
const pa = find ( a );
const pb = find ( b );
if ( pa !== pb ) {
p [ pa ] = pb ;
size -- ;
}
};
const n = grid . length ;
let size = n * n * 4 ;
const p = Array . from ({ length : size }, ( _ , i ) => i );
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
const k = i * n + j ;
if ( i < n - 1 ) {
union ( 4 * k + 2 , ( k + n ) * 4 );
}
if ( j < n - 1 ) {
union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 );
}
if ( grid [ i ][ j ] === '/' ) {
union ( 4 * k , 4 * k + 3 );
union ( 4 * k + 1 , 4 * k + 2 );
} else if ( grid [ i ][ j ] === '\\' ) {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 2 , 4 * k + 3 );
} else {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 1 , 4 * k + 2 );
union ( 4 * k + 2 , 4 * k + 3 );
}
}
}
return size ;
}
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 /**
* @param {string[]} grid
* @return {number}
*/
function regionsBySlashes ( grid ) {
const find = x => {
if ( p [ x ] !== x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
};
const union = ( a , b ) => {
const pa = find ( a );
const pb = find ( b );
if ( pa !== pb ) {
p [ pa ] = pb ;
size -- ;
}
};
const n = grid . length ;
let size = n * n * 4 ;
const p = Array . from ({ length : size }, ( _ , i ) => i );
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
const k = i * n + j ;
if ( i < n - 1 ) {
union ( 4 * k + 2 , ( k + n ) * 4 );
}
if ( j < n - 1 ) {
union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 );
}
if ( grid [ i ][ j ] === '/' ) {
union ( 4 * k , 4 * k + 3 );
union ( 4 * k + 1 , 4 * k + 2 );
} else if ( grid [ i ][ j ] === '\\' ) {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 2 , 4 * k + 3 );
} else {
union ( 4 * k , 4 * k + 1 );
union ( 4 * k + 1 , 4 * k + 2 );
union ( 4 * k + 2 , 4 * k + 3 );
}
}
}
return size ;
}
Solution 2: DFS
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71 function regionsBySlashes ( grid : string []) : number {
const createGraph = () => {
const n = grid . length ;
const g = Array . from ({ length : n * 2 }, () => Array ( n * 2 ). fill ( 0 ));
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
const [ y , x ] = [ i * 2 , j * 2 ];
switch ( grid [ i ][ j ]) {
case '/' :
g [ y ][ x ] = g [ y + 1 ][ x + 1 ] = 0 ;
g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = 1 ;
break ;
case '\\' :
g [ y ][ x ] = g [ y + 1 ][ x + 1 ] = 2 ;
g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = 0 ;
break ;
default :
g [ y ][ x ] = g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = g [ y + 1 ][ x + 1 ] = 0 ;
break ;
}
}
}
return g ;
};
const isValid = ( x : number ) => 0 <= x && x < n ;
const dfs = ( i : number , j : number ) => {
if ( ! isValid ( i ) || ! isValid ( j ) || g [ i ][ j ]) return ;
g [ i ][ j ] = - 1 ;
const dirs = [ - 1 , 0 , 1 , 0 , - 1 ];
const neighbours : number [] = [];
for ( let d = 0 ; d < 4 ; d ++ ) {
const [ y , x ] = [ i + dirs [ d ], j + dirs [ d + 1 ]];
if ( isValid ( y ) && isValid ( x )) {
dfs ( y , x );
neighbours . push ( g [ y ][ x ]);
} else {
neighbours . push ( - 1 );
}
}
const [ top , right , bottom , left ] = neighbours ;
if ( top === 1 && right === 1 ) dfs ( i - 1 , j + 1 );
if ( bottom === 1 && left === 1 ) dfs ( i + 1 , j - 1 );
if ( top === 2 && left === 2 ) dfs ( i - 1 , j - 1 );
if ( bottom === 2 && right === 2 ) dfs ( i + 1 , j + 1 );
};
const g = createGraph ();
const n = g . length ;
let res = 0 ;
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( g [ i ][ j ] === 0 ) {
dfs ( i , j );
res ++ ;
}
}
}
return res ;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71 function regionsBySlashes ( grid ) {
const createGraph = () => {
const n = grid . length ;
const g = Array . from ({ length : n * 2 }, () => Array ( n * 2 ). fill ( 0 ));
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
const [ y , x ] = [ i * 2 , j * 2 ];
switch ( grid [ i ][ j ]) {
case '/' :
g [ y ][ x ] = g [ y + 1 ][ x + 1 ] = 0 ;
g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = 1 ;
break ;
case '\\' :
g [ y ][ x ] = g [ y + 1 ][ x + 1 ] = 2 ;
g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = 0 ;
break ;
default :
g [ y ][ x ] = g [ y ][ x + 1 ] = g [ y + 1 ][ x ] = g [ y + 1 ][ x + 1 ] = 0 ;
break ;
}
}
}
return g ;
};
const isValid = x => 0 <= x && x < n ;
const dfs = ( i , j ) => {
if ( ! isValid ( i ) || ! isValid ( j ) || g [ i ][ j ]) return ;
g [ i ][ j ] = - 1 ;
const dirs = [ - 1 , 0 , 1 , 0 , - 1 ];
const neighbours = [];
for ( let d = 0 ; d < 4 ; d ++ ) {
const [ y , x ] = [ i + dirs [ d ], j + dirs [ d + 1 ]];
if ( isValid ( y ) && isValid ( x )) {
dfs ( y , x );
neighbours . push ( g [ y ][ x ]);
} else {
neighbours . push ( - 1 );
}
}
const [ top , right , bottom , left ] = neighbours ;
if ( top === 1 && right === 1 ) dfs ( i - 1 , j + 1 );
if ( bottom === 1 && left === 1 ) dfs ( i + 1 , j - 1 );
if ( top === 2 && left === 2 ) dfs ( i - 1 , j - 1 );
if ( bottom === 2 && right === 2 ) dfs ( i + 1 , j + 1 );
};
const g = createGraph ();
const n = g . length ;
let res = 0 ;
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( g [ i ][ j ] === 0 ) {
dfs ( i , j );
res ++ ;
}
}
}
return res ;
}