Given a m x n grid. Each cell of the grid represents a street. The street of grid[i][j] can be:

    • 1 which means a street connecting the left cell and the right cell.
    • 2 which means a street connecting the upper cell and the lower cell.
    • 3 which means a street connecting the left cell and the lower cell.
    • 4 which means a street connecting the right cell and the lower cell.
    • 5 which means a street connecting the left cell and the upper cell.
    • 6 which means a street connecting the right cell and the upper cell.

    image.png

    You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

    Notice that you are not allowed to change any street.

    Return true if there is a valid path in the grid or false otherwise.

    Example 1:

    image.png

    1. Input: grid = [[2,4,3],[6,5,2]]
    2. Output: true
    3. Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

    Example 2:

    image.png

    1. Input: grid = [[1,2,1],[1,2,1]]
    2. Output: false
    3. Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

    Example 3:

    1. Input: grid = [[1,1,2]]
    2. Output: false
    3. Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

    Example 4:

    1. Input: grid = [[1,1,1,1,1,1,3]]
    2. Output: true

    Example 5:

    1. Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
    2. Output: true

    Constraints:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 300
    • 1 <= grid[i][j] <= 6

    题意

    判断沿着一个由路径块组合成的路径能否从左上角走到右下角。

    思路

    定义4个方向：0 - 左，1 - 上，2 - 右，3 - 下。

    判断能否走到一个路径块[i, j]的几个判断依据：

    1. i、j坐标是否有效；
    2. 当前路径块与来时的上一个块是否相连。

    除了从第左上角的块走到下一个块有两种可能，从其他块走到下一个块都只有一种情况(即只能沿着路走且不能回头)。

    使用DFS处理。

    代码实现

    1. class Solution {
    2.     int m, n;
    3.     // 定义沿着左上右下四个方向走时坐标的变化
    4.     int[] iPlus = {0, -1, 0, 1};
    5.     int[] jPlus = {-1, 0, 1, 0};
    6.     int[][] path = {{0, 2}, {1, 3}, {0, 3}, {2, 3}, {0, 1}, {1, 2}};
    8.     public boolean hasValidPath(int[][] grid) {
    9.         m = grid.length;
    10.         n = grid[0].length;
    11.         if (m == 1 && n == 1) {
    12.             return true;
    13.         }
    14.         return judge(grid, -1, 0, 0);
    15.     }
    17.     // pre为从上一个路径块来时的方向
    18.     private boolean judge(int[][] grid, int pre, int i, int j) {
    19.         // 先判断i，j是否合法
    20.         if (i < 0 || i >= m || j < 0 || j >= n) {
    21.             return false;
    22.         }
    23.         // 当前路径块的类型及它连接的两个方向
    24.         int type = grid[i][j] - 1;
    25.         int directionA = path[type][0], directionB = path[type][1];
    26.         // 如果当前块是起点，需要向两个方向dfs
    27.         if (pre == -1) {
    28.             return judge(grid, (directionA + 2) % 4, i + iPlus[directionA], j + jPlus[directionA])
    29.                     || judge(grid, (directionB + 2) % 4, i + iPlus[directionB], j + jPlus[directionB]);
    30.         }
    31.         // 判断当前块与上一个路径块是否相连
    32.         if (pre != directionA && pre != directionB) {
    33.             return false;
    34.         }
    35.         // 已经走到右下角则直接返回
    36.         if (i == m - 1 && j == n - 1) {
    37.             return true;
    38.         }
    39.         // 沿着当前路径走到下一个路径块
    40.         int nextDir = pre == directionA ? directionB : directionA;
    41.         return judge(grid, (nextDir + 2) % 4, i + iPlus[nextDir], j + jPlus[nextDir]);
    42.     }
    43. }