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
Python3 Java C++ Go
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
}
GitHub