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:
![](https://spcdn.pages.dev/leetcode/problems/2510.Check%20if%20There%20is%20a%20Path%20With%20Equal%20Number%20of%200%27s%20And%201%27s/images/yetgriddrawio-4.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/2510.Check%20if%20There%20is%20a%20Path%20With%20Equal%20Number%20of%200%27s%20And%201%27s/images/yetgrid2drawio-1.png)
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#
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)
}
|