leetcode 1391. 检查网格中是否存在有效路径 中等

给你一个mxn的网格grid。网格里的每个单元都代表一条街道。grid[i][j]的街道可以是：

• 1表示连接左单元格和右单元格的街道。
• 2表示连接上单元格和下单元格的街道。
• 3表示连接左单元格和下单元格的街道。
• 4表示连接右单元格和下单元格的街道。
• 5表示连接左单元格和上单元格的街道。
• 6表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格(0,0)开始出发，网格中的「有效路径」是指从左上方的单元格(0,0)开始、一直到右下方的(m-1,n-1)结束的路径。该路径必须只沿着街道走。

注意：你不能变更街道。

如果网格中存在有效的路径，则返回true，否则返回false。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]输出：true解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]输出：false解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

示例 3：

输入：grid = [[1,1,2]]输出：false解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]输出：true

提示：

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

分析：从起点开始进行 BFS，用一个队列记录当前可以走到的街道位置，初始时队列里仅有起点的坐标位置。每次进行 BFS 时，检查队列头的坐标，根据它的街道形式，判断能否走到相邻的街和相邻的街道是否已经走到过，如果可以走到并且没有走过，则标记相邻街道已访问并入队，直到队列为空或者走到右下角。最后检查右下角是否走过，如果走过，返回 true，否则返回 false。

class Solution { public: bool hasValidPath(vector<vector<int>>& grid) { int x=0,y=0,f=1,m=grid.size(),n=grid[0].size(),flag[m+5][n+5]; for(int i=0;i<m;++i) for(int j=0;j<n;++j) flag[i][j]=0; stack<pair<int,int>>sta;sta.push({0,0}); while(!sta.empty()) { int xx=sta.top().first,yy=sta.top().second,f=0; flag[xx][yy]=1; if(grid[xx][yy]==1) { if(yy+1<n&&flag[xx][yy+1]==0&&(grid[xx][yy+1]==3||grid[xx][yy+1]==5||grid[xx][yy+1]==1)) sta.push({xx,yy+1}),f=1; if(yy-1>=0&&flag[xx][yy-1]==0&&(grid[xx][yy-1]==4||grid[xx][yy-1]==6||grid[xx][yy-1]==1)) sta.push({xx,yy-1}),f=1; } else if(grid[xx][yy]==2) { if(xx+1<m&&flag[xx+1][yy]==0&&(grid[xx+1][yy]==5||grid[xx+1][yy]==6||grid[xx+1][yy]==2)) sta.push({xx+1,yy}),f=1; if(xx-1>=0&&flag[xx-1][yy]==0&&(grid[xx-1][yy]==3||grid[xx-1][yy]==4||grid[xx-1][yy]==2)) sta.push({xx-1,yy}),f=1; } else if(grid[xx][yy]==3) { if(xx+1<m&&flag[xx+1][yy]==0&&(grid[xx+1][yy]==5||grid[xx+1][yy]==6||grid[xx+1][yy]==2)) sta.push({xx+1,yy}),f=1; if(yy-1>=0&&flag[xx][yy-1]==0&&(grid[xx][yy-1]==4||grid[xx][yy-1]==6||grid[xx][yy-1]==1)) sta.push({xx,yy-1}),f=1; } else if(grid[xx][yy]==4) { if(xx+1<m&&flag[xx+1][yy]==0&&(grid[xx+1][yy]==5||grid[xx+1][yy]==6||grid[xx+1][yy]==2)) sta.push({xx+1,yy}),f=1; if(yy+1<n&&flag[xx][yy+1]==0&&(grid[xx][yy+1]==3||grid[xx][yy+1]==5||grid[xx][yy+1]==1)) sta.push({xx,yy+1}),f=1; } else if(grid[xx][yy]==5) { if(xx-1>=0&&flag[xx-1][yy]==0&&(grid[xx-1][yy]==3||grid[xx-1][yy]==4||grid[xx-1][yy]==2)) sta.push({xx-1,yy}),f=1; if(yy-1>=0&&flag[xx][yy-1]==0&&(grid[xx][yy-1]==4||grid[xx][yy-1]==6||grid[xx][yy-1]==1)) sta.push({xx,yy-1}),f=1; } else if(grid[xx][yy]==6) { if(xx-1>=0&&flag[xx-1][yy]==0&&(grid[xx-1][yy]==3||grid[xx-1][yy]==4||grid[xx-1][yy]==2)) sta.push({xx-1,yy}),f=1; if(yy+1<n&&flag[xx][yy+1]==0&&(grid[xx][yy+1]==3||grid[xx][yy+1]==5||grid[xx][yy+1]==1)) sta.push({xx,yy+1}),f=1; } if(!f)sta.pop(); } if(flag[m-1][n-1]==1)return true; return false; } };