1391. Check if There is a Valid Path in a Grid

Time: O(m*n)

Space: O(m*n)

Intuition

Instead of manually validating every street-type pair at cell boundaries, expand each original cell into a 3x3 pixel block where valid street segments are drawn as connected true cells. Then the problem becomes a plain connectivity query: is there any continuous path from the expanded start center to expanded end center?

Algorithm

1Create a boolean grid of size (m*3) x (n*3).
2For each street type (1..6), mark the corresponding three pixels in that 3x3 block to represent its road shape.
3Start DFS from expanded coordinate (1,1), which is the center of top-left cell.
4During DFS, stop when out of bounds or on a false cell; otherwise mark current pixel visited and move in 4 directions.
5If DFS reaches (m*3-2, n*3-2), which is center of bottom-right cell, return true.
6If traversal ends without reaching destination, return false.

Example Walkthrough

Input: grid = [[2,4,3],[6,5,2]]

1.Build expanded map where each street draws its passable pixels.
2.From start center, DFS follows only connected road pixels.
3.Because neighboring street segments match, traversal can continue through the route.
4.Destination center is reached, so a valid path exists.

Output: true

Common Pitfalls

•Street encoding must be exact for each type; a wrong pixel pattern causes false positives/negatives.
•Always mark visited during DFS to prevent infinite recursion loops.
•This recursion can be deep on large grids; iterative DFS/BFS is an alternative if stack depth is a concern.

1391.cs

public class Solution
{
    // Approach: Expand each cell to a 3x3 mini-grid that encodes street connectivity,
    // then DFS from start to destination on expanded walkable pixels.
    // Time: O(m*n) Space: O(m*n)
    public bool HasValidPath(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        bool[,] g = new bool[m * 3, n * 3];

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                switch (grid[i][j])
                {
                    case 1:
                        g[i * 3 + 1, j * 3 + 0] = true;
                        g[i * 3 + 1, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 2] = true;
                        break;
                    case 2:
                        g[i * 3 + 0, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 1] = true;
                        g[i * 3 + 2, j * 3 + 1] = true;
                        break;
                    case 3:
                        g[i * 3 + 1, j * 3 + 0] = true;
                        g[i * 3 + 1, j * 3 + 1] = true;
                        g[i * 3 + 2, j * 3 + 1] = true;
                        break;
                    case 4:
                        g[i * 3 + 1, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 2] = true;
                        g[i * 3 + 2, j * 3 + 1] = true;
                        break;
                    case 5:
                        g[i * 3 + 0, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 0] = true;
                        g[i * 3 + 1, j * 3 + 1] = true;
                        break;
                    case 6:
                        g[i * 3 + 0, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 1] = true;
                        g[i * 3 + 1, j * 3 + 2] = true;
                        break;
                }
            }
        }

        return Dfs(g, 1, 1);
    }

    private bool Dfs(bool[,] g, int i, int j)
    {
        if (i < 0 || i == g.GetLength(0) || j < 0 || j == g.GetLength(1))
            return false;
        if (!g[i, j]) // There's no path here.
            return false;
        if (i == g.GetLength(0) - 2 && j == g.GetLength(1) - 2)
            return true;

        g[i, j] = false; // Mark as visited.
        return Dfs(g, i + 1, j) || Dfs(g, i - 1, j) || Dfs(g, i, j + 1) || Dfs(g, i, j - 1);
    }
}

Was this solution helpful?