Breadth-First Search
Array
Matrix
Description
You are given an m x n
grid rooms
initialized with these three possible values.
-1
A wall or an obstacle.
0
A gate.
INF
Infinity means an empty room. We use the value 231 - 1 = 2147483647
to represent INF
as you may assume that the distance to a gate is less than 2147483647
.
Fill each empty room with the distance to its nearest gate . If it is impossible to reach a gate, it should be filled with INF
.
Example 1:
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Example 2:
Input: rooms = [[-1]]
Output: [[-1]]
Constraints:
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j]
is -1
, 0
, or 231 - 1
.
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 class Solution :
def wallsAndGates ( self , rooms : List [ List [ int ]]) -> None :
"""
Do not return anything, modify rooms in-place instead.
"""
m , n = len ( rooms ), len ( rooms [ 0 ])
inf = 2 ** 31 - 1
q = deque ([( i , j ) for i in range ( m ) for j in range ( n ) if rooms [ i ][ j ] == 0 ])
d = 0
while q :
d += 1
for _ in range ( len ( q )):
i , j = q . popleft ()
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 rooms [ x ][ y ] == inf :
rooms [ x ][ y ] = d
q . append (( 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 class Solution {
public void wallsAndGates ( int [][] rooms ) {
int m = rooms . length ;
int n = rooms [ 0 ] . length ;
Deque < int []> q = new LinkedList <> ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( rooms [ i ][ j ] == 0 ) {
q . offer ( new int [] { i , j });
}
}
}
int d = 0 ;
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
while ( ! q . isEmpty ()) {
++ d ;
for ( int i = q . size (); i > 0 ; -- i ) {
int [] p = q . poll ();
for ( int j = 0 ; j < 4 ; ++ j ) {
int x = p [ 0 ] + dirs [ j ] ;
int y = p [ 1 ] + dirs [ j + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n && rooms [ x ][ y ] == Integer . MAX_VALUE ) {
rooms [ x ][ y ] = d ;
q . offer ( new int [] { 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 class Solution {
public :
void wallsAndGates ( vector < vector < int >>& rooms ) {
int m = rooms . size ();
int n = rooms [ 0 ]. size ();
queue < pair < int , int >> q ;
for ( int i = 0 ; i < m ; ++ i )
for ( int j = 0 ; j < n ; ++ j )
if ( rooms [ i ][ j ] == 0 )
q . emplace ( i , j );
int d = 0 ;
vector < int > dirs = { -1 , 0 , 1 , 0 , -1 };
while ( ! q . empty ()) {
++ d ;
for ( int i = q . size (); i > 0 ; -- i ) {
auto p = q . front ();
q . pop ();
for ( int j = 0 ; j < 4 ; ++ j ) {
int x = p . first + dirs [ j ];
int y = p . second + dirs [ j + 1 ];
if ( x >= 0 && x < m && y >= 0 && y < n && rooms [ x ][ y ] == INT_MAX ) {
rooms [ x ][ y ] = d ;
q . emplace ( 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 func wallsAndGates ( rooms [][] int ) {
m , n := len ( rooms ), len ( rooms [ 0 ])
var q [][] int
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if rooms [ i ][ j ] == 0 {
q = append ( q , [] int { i , j })
}
}
}
d := 0
dirs := [] int { - 1 , 0 , 1 , 0 , - 1 }
for len ( q ) > 0 {
d ++
for i := len ( q ); i > 0 ; i -- {
p := q [ 0 ]
q = q [ 1 :]
for j := 0 ; j < 4 ; j ++ {
x , y := p [ 0 ] + dirs [ j ], p [ 1 ] + dirs [ j + 1 ]
if x >= 0 && x < m && y >= 0 && y < n && rooms [ x ][ y ] == math . MaxInt32 {
rooms [ x ][ y ] = d
q = append ( q , [] int { x , y })
}
}
}
}
}
GitHub