Array
Dynamic Programming
Matrix
Description
You are given a 0-indexed m x n
binary matrix grid
. You can move from a cell (row, col)
to any of the cells (row + 1, col)
or (row, col + 1)
.
Return true
if there is a path from (0, 0)
to (m - 1, n - 1)
that visits an equal number of 0
's and 1
's . Otherwise return false
.
Example 1:
Input: grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]
Output: true
Explanation: The path colored in blue in the above diagram is a valid path because we have 3 cells with a value of 1 and 3 with a value of 0. Since there is a valid path, we return true.
Example 2:
Input: grid = [[1,1,0],[0,0,1],[1,0,0]]
Output: false
Explanation: There is no path in this grid with an equal number of 0's and 1's.
Constraints:
m == grid.length
n == grid[i].length
2 <= m, n <= 100
grid[i][j]
is either 0
or 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
19 class Solution :
def isThereAPath ( self , grid : List [ List [ int ]]) -> bool :
@cache
def dfs ( i , j , k ):
if i >= m or j >= n :
return False
k += grid [ i ][ j ]
if k > s or i + j + 1 - k > s :
return False
if i == m - 1 and j == n - 1 :
return k == s
return dfs ( i + 1 , j , k ) or dfs ( i , j + 1 , k )
m , n = len ( grid ), len ( grid [ 0 ])
s = m + n - 1
if s & 1 :
return False
s >>= 1
return dfs ( 0 , 0 , 0 )
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 class Solution {
private int s ;
private int m ;
private int n ;
private int [][] grid ;
private Boolean [][][] f ;
public boolean isThereAPath ( int [][] grid ) {
m = grid . length ;
n = grid [ 0 ] . length ;
this . grid = grid ;
s = m + n - 1 ;
f = new Boolean [ m ][ n ][ s ] ;
if ( s % 2 == 1 ) {
return false ;
}
s >>= 1 ;
return dfs ( 0 , 0 , 0 );
}
private boolean dfs ( int i , int j , int k ) {
if ( i >= m || j >= n ) {
return false ;
}
k += grid [ i ][ j ] ;
if ( f [ i ][ j ][ k ] != null ) {
return f [ i ][ j ][ k ] ;
}
if ( k > s || i + j + 1 - k > s ) {
return false ;
}
if ( i == m - 1 && j == n - 1 ) {
return k == s ;
}
f [ i ][ j ][ k ] = dfs ( i + 1 , j , k ) || dfs ( i , j + 1 , k );
return f [ i ][ j ][ k ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
bool isThereAPath ( vector < vector < int >>& grid ) {
int m = grid . size (), n = grid [ 0 ]. size ();
int s = m + n - 1 ;
if ( s & 1 ) return false ;
int f [ m ][ n ][ s ];
s >>= 1 ;
memset ( f , -1 , sizeof f );
function < bool ( int , int , int ) > dfs = [ & ]( int i , int j , int k ) -> bool {
if ( i >= m || j >= n ) return false ;
k += grid [ i ][ j ];
if ( f [ i ][ j ][ k ] != -1 ) return f [ i ][ j ][ k ];
if ( k > s || i + j + 1 - k > s ) return false ;
if ( i == m - 1 && j == n - 1 ) return k == s ;
f [ i ][ j ][ k ] = dfs ( i + 1 , j , k ) || dfs ( i , j + 1 , k );
return f [ i ][ j ][ k ];
};
return dfs ( 0 , 0 , 0 );
}
};
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 func isThereAPath ( grid [][] int ) bool {
m , n := len ( grid ), len ( grid [ 0 ])
s := m + n - 1
if s % 2 == 1 {
return false
}
s >>= 1
f := [ 100 ][ 100 ][ 200 ] int {}
var dfs func ( i , j , k int ) bool
dfs = func ( i , j , k int ) bool {
if i >= m || j >= n {
return false
}
k += grid [ i ][ j ]
if f [ i ][ j ][ k ] != 0 {
return f [ i ][ j ][ k ] == 1
}
f [ i ][ j ][ k ] = 2
if k > s || i + j + 1 - k > s {
return false
}
if i == m - 1 && j == n - 1 {
return k == s
}
res := dfs ( i + 1 , j , k ) || dfs ( i , j + 1 , k )
if res {
f [ i ][ j ][ k ] = 1
}
return res
}
return dfs ( 0 , 0 , 0 )
}
GitHub