目标
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
- 1 表示连接左单元格和右单元格的街道。
- 2 表示连接上单元格和下单元格的街道。
- 3 表示连接左单元格和下单元格的街道。
- 4 表示连接右单元格和下单元格的街道。
- 5 表示连接左单元格和上单元格的街道。
- 6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：
输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。示例 2：
输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。示例 3：
输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。示例 4：
输入：grid = [[1,1,1,1,1,1,3]]
输出：true示例 5：
输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- 1 <= grid[i][j] <= 6
思路
有一个二维矩阵 grid，每个单元格的值都代表一种街道类型，判断能否从左上角出发沿着街道走到右下角。
根据当前的街道类型，初始化可走的方向，同时判断下一个位置是否超出了边界，是否访问过，是否与当前街道连通。
代码
/**
* @date 2026-04-27 9:08
*/
public class HasValidPath1391 {
public boolean hasValidPath(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
return dfs(0, 0, new int[]{1, 2, 3, 4, 5, 6}, visited, grid);
}
public static int[][][] directions = new int[][][]{
{{0, 0}, {0, 0}},
{{0, -1}, {0, 1}},
{{-1, 0}, {1, 0}},
{{0, -1}, {1, 0}},
{{0, 1}, {1, 0}},
{{0, -1}, {-1, 0}},
{{0, 1}, {-1, 0}},
};
public static int[][][] allowedTypes = new int[][][]{
{{}},
{{1, 4, 6}, {1, 3, 5}},
{{2, 3, 4}, {2, 5, 6}},
{{1, 4, 6}, {2, 5, 6}},
{{1, 3, 5}, {2, 5, 6}},
{{1, 4, 6}, {2, 3, 4}},
{{1, 3, 5}, {2, 3, 4}},
};
public boolean dfs(int row, int col, int[] types, boolean[][] visited, int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if (row == m || row < 0 || col == n || col < 0 || visited[row][col]) {
return false;
}
visited[row][col] = true;
int type = grid[row][col];
boolean valid = false;
for (int t : types) {
if (t == type) {
valid = true;
break;
}
}
if (!valid) {
return false;
}
boolean res = row == m - 1 && col == n - 1;
for (int i = 0; i < directions[type].length; i++) {
res = res || dfs(row + directions[type][i][0], col + directions[type][i][1], allowedTypes[type][i], visited, grid);
}
return res;
}
}
性能
