题目链接：https://leetcode-cn.com/problems/check-if-there-is-a-valid-path-in-a-grid/

思路：就是一道比较直接的dfs题，只不过状态表示比较费劲。感觉我写的比较简洁，就传上来了。

算法：dfs

时间复杂度：$O(n)$

需要注意的地方：
1.
这段代码，用grid代替了st，然后在记录道路的的类型的数组,road[0]是全0的，表示这个地方哪里都不通。当然在标记之前要先取到类型。
2.
要注意road数组和dx，dy数组之间方向的顺序要一致。便于枚举四个方向。

class Solution {
public:
    int road[7][4] = {
        {0, 0, 0, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}, {0, 0, 1, 1}, 
        {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 1, 0, 0}
    };
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上右下左

    bool hasValidPath(vector<vector<int>>& grid) {
        dfs(0, 0, grid);
        return grid[grid.size() - 1][grid[0].size() - 1] == 0;
    }

    void dfs(int a, int b, vector<vector<int>> & grid){
        int type = grid[a][b];
        grid[a][b] = 0;//标记
        for(int i = 0; i < 4; i ++ ){//四个方向
            int c = a + dx[i], d = b + dy[i];
            if(c >= 0 && c < grid.size() && d >= 0 && d < grid[0].size())//坐标合法
                if(road[type][i] == 1 && road[grid[c][d]][(i + 2) % 4] == 1)
                    dfs(c, d, grid);
        }
    }
};