5366. 檢查網格中是否存在有效路徑

思路：分好上下左右的情況即可，比bfs，dfs那些簡單一點。從0，0開始，走到m-1,n-1就返回true，go_next(判斷下一步)

class Solution {
public:bool hasValidPath(vector<vector<int>>& grid) {m=grid.size();n=grid[0].size();fill(flag[0], flag[0]+300*300, false);return go_next(0,0,grid);}
private:int m,n;bool flag[300][300];//記錄走過的 vector<vector<int> > v={{-1,0},{1,0},{0,-1},{0,1}};//上下左右 bool go_next(int x,int y,vector<vector<int>>& grid){if(x==m-1&&y==n-1) return true;flag[x][y]=true;printf("%d %d\n",x,y);for(int i=0;i<4;i++){int new_x=x+v[i][0];int new_y=y+v[i][1];if(new_x>=0&&new_x<m&&new_y>=0&&new_y<n&&!flag[new_x][new_y]){if(i==0){//上 if((grid[x][y]==2||grid[x][y]==5||grid[x][y]==6)&&(grid[new_x][new_y]==2||grid[new_x][new_y]==3||grid[new_x][new_y]==4))return go_next(new_x,new_y, grid);}else if(i==1){//下 if((grid[x][y]==2||grid[x][y]==3||grid[x][y]==4)&&(grid[new_x][new_y]==2||grid[new_x][new_y]==5||grid[new_x][new_y]==6))return go_next(new_x,new_y, grid);}else if(i==2){//左 if((grid[x][y]==1||grid[x][y]==3||grid[x][y]==5)&&(grid[new_x][new_y]==1||grid[new_x][new_y]==4||grid[new_x][new_y]==6))return go_next(new_x,new_y, grid);}else if(i==3){//右 if((grid[x][y]==1||grid[x][y]==4||grid[x][y]==6)&&(grid[new_x][new_y]==1||grid[new_x][new_y]==3||grid[new_x][new_y]==5))return go_next(new_x,new_y, grid);}}}return false; }
};

?