Loading problem…
You are given an 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. You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that 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
Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: Starting at (0,0), street 2 leads down to (1,0). Street 6 turns right to (1,1), street 5 turns up to (0,1), street 4 turns right to (0,2), street 3 turns down to (1,2). Every step connects on both sides, and we reach the bottom-right cell.
Example 2
Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: Street 1 at (0,0) leads right to (0,1), but street 2 there only opens up and down. It does not connect back to the left, so the path is blocked.
Example 3
Input: grid = [[1,1,2]]
Output: false
Explanation: The path moves right through (0,0) and (0,1), but street 2 at (0,2) does not open to the left, so we can never enter the last cell.
Each cell type lists exactly two neighbour directions it connects to. So the streets form an undirected graph: there's an edge between cells `A` and `B` if and only if `A`'s street points to `B` *and* `B`'s street points back to `A`. The question becomes a standard reachability check from the top-left to the bottom-right — easy with BFS.
Run checks all cases above. Submit evaluates all test cases.