class Solution { public: bool res=false; bool hasValidPath(vector<vector<int>>& grid) { vector<vector<bool>> visit(grid.size(),vector<bool>(grid[0].size(),false)); DFS(grid,visit,0,0); return res; } void DFS(vector<vector<int>>& grid,vector<vector<bool>>& visit,int i,int j) { visit[i][j]=true; if(i==grid.size()-1 && j==grid[0].size()-1) { res=true; return; } if(grid[i][j]==1) { if(j+1<grid[0].size() && !visit[i][j+1] && (grid[i][j+1]==1 ||grid[i][j+1]==3 || grid[i][j+1]==5)) { DFS(grid,visit,i,j+1); } if(j-1>=0 && !visit[i][j-1] && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6)) { DFS(grid,visit,i,j-1); } } if(grid[i][j]==2) { if(i+1<grid.size() && !visit[i+1][j] && (grid[i+1][j]==2 || grid[i+1][j]==5 || grid[i+1][j]==6)) { DFS(grid,visit,i+1,j); } if(i-1>=0 && !visit[i-1][j] && (grid[i-1][j]==2 ||grid[i-1][j]==3 || grid[i-1][j]==4)) { DFS(grid,visit,i-1,j); } } if(grid[i][j]==3) { if(i+1<grid.size() && !visit[i+1][j] && (grid[i+1][j]==2 ||grid[i+1][j]==5 || grid[i+1][j]==6)) { DFS(grid,visit,i+1,j); } if(j-1>=0 && !visit[i][j-1] && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6 )) { DFS(grid,visit,i,j-1); } } if(grid[i][j]==4) { if(i+1<grid.size() && !visit[i+1][j] && (grid[i+1][j]==2 ||grid[i+1][j]==5 || grid[i+1][j]==6)) { DFS(grid,visit,i+1,j); } if(j+1<=grid[0].size() && !visit[i][j+1] && (grid[i][j+1]==1 || grid[i][j+1]==3 || grid[i][j+1]==5)) { DFS(grid,visit,i,j+1); } } if(grid[i][j]==5) { if(i-1>=0 && !visit[i-1][j] && (grid[i-1][j]==2 ||grid[i-1][j]==3 || grid[i-1][j]==4)) { DFS(grid,visit,i-1,j); } if(j-1>=0 && !visit[i][j-1] && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6 )) { DFS(grid,visit,i,j-1); } } if(grid[i][j]==6) { if(i-1>=0 && !visit[i-1][j] && (grid[i-1][j]==2 ||grid[i-1][j]==3 || grid[i-1][j]==4)) { DFS(grid,visit,i-1,j); } if(j+1<=grid[0].size() && !visit[i][j+1] && (grid[i][j+1]==1 || grid[i][j+1]==3 || grid[i][j+1]==5)) { DFS(grid,visit,i,j+1); } } visit[i][j]=false; return; } };