Check if There is a Valid Path in a Grid

This approach models the grid as a graph where each cell is a node. An edge exists between two adjacent cells if their respective streets connect to each other. The problem then becomes finding if a path exists from the source node (0, 0) to the destination node (m-1, n-1). DFS is a natural way to explore this path.

• We model the grid as a graph where each cell is a node. An edge exists between two adjacent cells if their respective streets connect to each other. The problem then becomes finding if a path exists from the source node (0, 0) to the destination node (m-1, n-1).
• We start a traversal from the cell (0, 0).
• We use a visited boolean grid to keep track of cells that are already part of the current exploration path to avoid cycles and redundant computations.
• The core of the approach is a recursive function, say dfs(row, col), which explores paths from the current cell (row, col).
• Algorithm Steps:
  1. Define the possible moves for each street type. A street k allows moves in two directions. We can store this in a 3D array, e.g., moves[k-1] = {{dr1, dc1}, {dr2, dc2}}.
  2. Create a recursive function dfs(r, c, grid, visited).
  3. Base Case: If (r, c) is the destination (m-1, n-1), a path is found, return true.
  4. Mark the current cell (r, c) as visited.
  5. Get the current street type type = grid[r][c].
  6. Iterate through the two possible moves (dr, dc) for this type.
  7. For each move, calculate the neighbor's coordinates (nr, nc) = (r + dr, c + dc).
  8. Validity Checks:
     • Check if (nr, nc) is within the grid boundaries.
     • Check if (nr, nc) has been visited.
     • Crucially, check if the street at (nr, nc) connects back to (r, c). This means one of the allowed moves from (nr, nc) must be (-dr, -dc).
  9. If the move is valid, make a recursive call dfs(nr, nc, grid, visited). If this call returns true, it means a path to the destination was found, so propagate true up the call stack.
  10. The initial call is dfs(0, 0, grid, visited).

class Solution {
    // directions[street_type - 1] = {{dr1, dc1}, {dr2, dc2}}
    private int[][][] directions = {
        {{0, -1}, {0, 1}},   // 1: left-right
        {{-1, 0}, {1, 0}},   // 2: up-down
        {{0, -1}, {1, 0}},   // 3: left-down
        {{0, 1}, {1, 0}},    // 4: right-down
        {{0, -1}, {-1, 0}},  // 5: left-up
        {{0, 1}, {-1, 0}}    // 6: right-up
    };
    private int m, n;
    private boolean[][] visited;

    public boolean hasValidPath(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        return dfs(0, 0, grid);
    }

    private boolean dfs(int r, int c, int[][] grid) {
        if (r == m - 1 && c == n - 1) {
            return true;
        }
        visited[r][c] = true;

        int streetType = grid[r][c];
        for (int[] dir : directions[streetType - 1]) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                // Check if the next street connects back
                int nextStreetType = grid[nr][nc];
                for (int[] backDir : directions[nextStreetType - 1]) {
                    if (nr + backDir[0] == r && nc + backDir[1] == c) {
                        if (dfs(nr, nc, grid)) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}