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

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.

![](https://assets.leetcode.com/uploads/2020/03/05/main.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:**![](https://assets.leetcode.com/uploads/2020/03/05/e1.png)

```
Input: grid = [[2,4,3],[6,5,2]]
Output: true
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:**![](https://assets.leetcode.com/uploads/2020/03/05/e2.png)

```
Input: grid = [[1,2,1],[1,2,1]]
Output: false
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:**

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

**Example 4:**

```
Input: grid = [[1,1,1,1,1,1,3]]
Output: true
```

**Example 5:**

```
Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true
```

**Constraints:**

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

给由如图所示拼图组成的地图，问能否从(0, 0)走到(M-1, N-1)。实体图能否到达=>BFS/DFS。将拼图encode成可以走的方向，检查下个点是否可达，可达时再检查能否从下个点回来，如果都能说明下个点和当前点确实是通的。

```python
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m = len(grid) 
        n = len(grid[0])
        v = [[False] * n for i in range(m)]
        dirs = [[(0, -1), (0, 1)], 
                [(-1, 0), (1, 0)], 
                [(0, -1), (1, 0)],
                [(1, 0), (0, 1)],
                [(-1, 0), (0, -1)],
                [(-1, 0), (0, 1)]]
        q = [(0, 0)]
        v[0][0] = True
        while len(q) != 0:
            t = q[0]
            q.pop(0)
            for _, d in enumerate(dirs[grid[t[0]][t[1]] - 1]):
                r = t[0] + d[0]
                c = t[1] + d[1]
                if r >= 0 and r < m and c >= 0 and c < n and not v[r][c]:
                    for _, nd in enumerate(dirs[grid[r][c] - 1]):
                        if r + nd[0] == t[0] and c + nd[1] == t[1]:
                            q.append((r, c))
                            v[r][c] = True
        return v[m - 1][n - 1]
                
                
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/search/1391.-check-if-there-is-a-valid-path-in-a-grid.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.