题目描述

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

• 1 表示连接左单元格和右单元格的街道。
• 2 表示连接上单元格和下单元格的街道。
• 3 表示连接左单元格和下单元格的街道。
• 4 表示连接右单元格和下单元格的街道。
• 5 表示连接左单元格和上单元格的街道。
• 6 表示连接右单元格和上单元格的街道。
  给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
  

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你 不能 变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

样例

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

输入：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

算法分析

dfs
方向：0表示左，1表示上，2表示右，3表示下

• dir[i][]数组，表示第i个Street可以往哪些方向走，例如：第1个街道可以往左(0)，右(2)方向走，因此dir[1][0] = 0,dir[1][1] = 2

• check(dd,op2)：表示op2街道是否能和dd方向衔接上，其中dd表示去到op2街道的方向

从(0,0)位置开始往四周dfs，若当前位置是(i,j)，且假设(i,j)四周的位置是(a,b),若(a,b)位置未遍历过且(i,j)能和(a,b)的街道模型能衔接上，则继续dfs到(a,b)

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static int N = 310;
    static int n,m;
    static boolean[][] st = new boolean[N][N];
    static int[] dx = new int[]{0,-1,0,1};
    static int[] dy = new int[]{-1,0,1,0};
    static int[][] dir = new int[][]{{-1,-1},{0,2},{1,3},{0,3},{2,3},{0,1},{1,2}};

    static boolean check(int dd,int op2)
    {
        int one = (dir[op2][0] + 2) % 4;
        int two = (dir[op2][1] + 2) % 4;
        if(dd == one || dd == two) return true;
        return false;
    }
    static boolean dfs(int x,int y,int[][] grid)
    {
        int op = grid[x][y];
        st[x][y] = true;
        if(x == n - 1 && y == m - 1) return true;
        for(int i = 0;i < 2;i ++)
        {
            int dd = dir[op][i];//从(x,y)走到(a,b)的方向
            int a = x + dx[dd];
            int b = y + dy[dd];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[a][b]) continue;
            if(check(dd,grid[a][b]) && dfs(a,b,grid)) return true;   
        }
        return false;
    }
    public boolean hasValidPath(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        for(int i = 0;i < n;i ++) Arrays.fill(st[i],false);

        return dfs(0,0,grid);
    }
}