给你一个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.lengthn grid[i].length1 m, n 3001 grid[i][j] 6分析从起点开始进行 BFS用一个队列记录当前可以走到的街道位置初始时队列里仅有起点的坐标位置。每次进行 BFS 时检查队列头的坐标根据它的街道形式判断能否走到相邻的街和相邻的街道是否已经走到过如果可以走到并且没有走过则标记相邻街道已访问并入队直到队列为空或者走到右下角。最后检查右下角是否走过如果走过返回 true否则返回 false。class Solution { public: bool hasValidPath(vectorvectorint grid) { int x0,y0,f1,mgrid.size(),ngrid[0].size(),flag[m5][n5]; for(int i0;im;i) for(int j0;jn;j) flag[i][j]0; stackpairint,intsta;sta.push({0,0}); while(!sta.empty()) { int xxsta.top().first,yysta.top().second,f0; flag[xx][yy]1; if(grid[xx][yy]1) { if(yy1nflag[xx][yy1]0(grid[xx][yy1]3||grid[xx][yy1]5||grid[xx][yy1]1)) sta.push({xx,yy1}),f1; if(yy-10flag[xx][yy-1]0(grid[xx][yy-1]4||grid[xx][yy-1]6||grid[xx][yy-1]1)) sta.push({xx,yy-1}),f1; } else if(grid[xx][yy]2) { if(xx1mflag[xx1][yy]0(grid[xx1][yy]5||grid[xx1][yy]6||grid[xx1][yy]2)) sta.push({xx1,yy}),f1; if(xx-10flag[xx-1][yy]0(grid[xx-1][yy]3||grid[xx-1][yy]4||grid[xx-1][yy]2)) sta.push({xx-1,yy}),f1; } else if(grid[xx][yy]3) { if(xx1mflag[xx1][yy]0(grid[xx1][yy]5||grid[xx1][yy]6||grid[xx1][yy]2)) sta.push({xx1,yy}),f1; if(yy-10flag[xx][yy-1]0(grid[xx][yy-1]4||grid[xx][yy-1]6||grid[xx][yy-1]1)) sta.push({xx,yy-1}),f1; } else if(grid[xx][yy]4) { if(xx1mflag[xx1][yy]0(grid[xx1][yy]5||grid[xx1][yy]6||grid[xx1][yy]2)) sta.push({xx1,yy}),f1; if(yy1nflag[xx][yy1]0(grid[xx][yy1]3||grid[xx][yy1]5||grid[xx][yy1]1)) sta.push({xx,yy1}),f1; } else if(grid[xx][yy]5) { if(xx-10flag[xx-1][yy]0(grid[xx-1][yy]3||grid[xx-1][yy]4||grid[xx-1][yy]2)) sta.push({xx-1,yy}),f1; if(yy-10flag[xx][yy-1]0(grid[xx][yy-1]4||grid[xx][yy-1]6||grid[xx][yy-1]1)) sta.push({xx,yy-1}),f1; } else if(grid[xx][yy]6) { if(xx-10flag[xx-1][yy]0(grid[xx-1][yy]3||grid[xx-1][yy]4||grid[xx-1][yy]2)) sta.push({xx-1,yy}),f1; if(yy1nflag[xx][yy1]0(grid[xx][yy1]3||grid[xx][yy1]5||grid[xx][yy1]1)) sta.push({xx,yy1}),f1; } if(!f)sta.pop(); } if(flag[m-1][n-1]1)return true; return false; } };
