You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:


	1 which means a street connecting the left cell and the right cell.
	2 which means a street connecting the upper cell and the lower cell.
	3 which means a street connecting the left cell and the lower cell.
	4 which means a street connecting the right cell and the lower cell.
	5 which means a street connecting the left cell and the upper cell.
	6 which means a street connecting the right cell and the upper cell.


You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

&nbsp;
Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).


Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)


Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 300
	1 &lt;= grid[i][j] &lt;= 6


class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        r,c=len(grid),len(grid[0])
        dic={
            2:[(-1,0),(1,0)],
            1:[(0,1),(0,-1)],
            5:[(-1,0),(0,-1)],
            3:[(1,0),(0,-1)],
            6:[(0,1),(-1,0)],
            4:[(0,1),(1,0)]
            
        }
        q=collections.deque([(0,0)])
        visit=set()
        while q:
            i,j=q.popleft()
            visit.add((i,j))
            if i==r-1 and j==c-1:
                return True
            for x,y in dic[grid[i][j]]:
                nx=i+x
                ny=j+y
                if nx>=0 and nx<r and ny>=0 and ny<c and (nx,ny) not in visit:
                    if (-x,-y) in dic[grid[nx][ny]]:
                        q.append((nx,ny))
        return False
class Solution {
    public boolean hasValidPath(int[][] grid) {
        int m=grid.length, n=grid[0].length;
        int[][] visited=new int[m][n];
        return dfs(grid, 0, 0, m, n, visited);
    }
    public boolean dfs(int[][] grid, int i, int j, int m, int n, int[][] visited){
        if(i==m-1 && j==n-1) return true;
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j]==1) return false;
        visited[i][j]=1;
        if(grid[i][j]==1){
            if( (j>0 && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6) && dfs(grid, i, j-1, m, n, visited)) || 
			    (j<n-1 && (grid[i][j+1]==1 || grid[i][j+1]==3 || grid[i][j+1]==5 ) && dfs(grid, i, j+1, m, n, visited) )) return true;
        }else if(grid[i][j]==2){
            if( (i<m-1 && (grid[i+1][j]==2 || grid[i+1][j]==5 || grid[i+1][j]==6) && dfs(grid, i+1, j, m, n, visited)) || 
                (i>0 && (grid[i-1][j]==2 || grid[i-1][j]==3 || grid[i-1][j]==4) && dfs(grid, i-1, j, m, n, visited))) return true;
        }else if(grid[i][j]==3){
            if( (j>0 && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6) && dfs(grid, i, j-1, m, n, visited)) || 
			    (i<m-1 && (grid[i+1][j]==2 || grid[i+1][j]==5 || grid[i+1][j]==6) && dfs(grid, i+1, j, m, n, visited))) return true;
        }else if(grid[i][j]==4){
            if( ((i<m-1 && (grid[i+1][j]==2 || grid[i+1][j]==5 || grid[i+1][j]==6)) && dfs(grid, i+1, j, m, n, visited)) || 
			    (j<n-1 && (grid[i][j+1]==1 || grid[i][j+1]==3 || grid[i][j+1]==5) && dfs(grid, i, j+1, m, n, visited))) return true;
        }else if(grid[i][j]==5){
            if( (j>0 && (grid[i][j-1]==1 || grid[i][j-1]==4 || grid[i][j-1]==6) && dfs(grid, i, j-1, m, n, visited)) || 
			    (i>0 && (grid[i-1][j]==2 || grid[i-1][j]==3 || grid[i-1][j]==4) && dfs(grid, i-1, j, m, n, visited))) return true;
        }else{
            if( (i>0 && (grid[i-1][j]==2 || grid[i-1][j]==3 || grid[i-1][j]==4) && dfs(grid, i-1, j, m, n, visited)) || 
			    (j<n-1 && (grid[i][j+1]==1 || grid[i][j+1]==3 || grid[i][j+1]==5) && dfs(grid, i, j+1, m, n, visited))) return true;
        }
        return false;
    }
}
class Solution {
public:
    
    bool hasValidPath(vector<vector<int>>& grid) 
    {
        int m = grid.size();
        int n = grid[0].size();
        if(m==1 and n==1) return true;
        // 2D - direction vector for all streets
        // 0th based indexing 0 to 11
        
        // Let grid value g[i][j] = 4, means we need to follow "street-4" direction
        // First index of street-4 direction = 2*(4-1) = 6
        // Second index of street-4 direction = 2*(4-1)+1 = 7
        // dir[6] = {0, 1}
        // dir[7] = {1, 0}
        vector<vector<int>>dir = {        // Indices   
            {0,-1}, {0, 1}, // street 1  -->  0  1
            {-1,0}, {1, 0}, // street 2  -->  2  3
            {0,-1}, {1, 0}, // street 3  -->  4  5
            {0, 1}, {1, 0}, // street 4  -->  6  7
            {0,-1}, {-1,0}, // street 5  -->  8  9 
            {0, 1}, {-1,0}  // street 6  -->  10  11
        };

        vector<vector<bool>>vis(m, vector<bool>(n, false));
        queue<pair<int,int>>q;
        
        q.push({0, 0});
        vis[0][0] = true;
        
        while (!q.empty()) 
        {
            auto cur = q.front(); q.pop();

            int r = cur.first;
            int c = cur.second;
            int val = grid[r][c] - 1; // grid values 1 to 6
            
            if(r==m-1 and c==n-1) return true;
            
            // 2 directions from every cell
            for(int k=0;k<2;k++) // k = 0, k = 1
            {
                int idx = 2*val+k;   // get index
                int nr = r + dir[idx][0];
                int nc = c + dir[idx][1];
                if (nr < 0 or nr >= m or nc < 0 or nc >= n or vis[nr][nc]==true) continue;
                
                //  for checking the back direction matches with current cell i.e forming path to next cell
                for(int x=0;x<2;x++)
                {
                    int i = 2*(grid[nr][nc]-1)+x;   // get index
                    if(r == nr+dir[i][0] and c == nc+dir[i][1]){
                        vis[nr][nc] = true;
                        q.push({nr, nc});
                    }       
                }
            }
        }
        return false;
    }
};
var hasValidPath = function(grid) {
	if (grid[0][0] === 5) return false;

	const M = grid.length, N = grid[0].length;
	const SEGMENTS = {
		1: {dirs: [[0,-1], [0,1]], adjs: [[1,4,6], [1,3,5]]},
		2: {dirs: [[-1,0], [1,0]], adjs: [[2,3,4], [2,5,6]]},
		3: {dirs: [[0,-1], [1,0]], adjs: [[1,4,6], [2,5,6]]},
		4: {dirs: [[0,1],  [1,0]], adjs: [[1,3,5], [2,5,6]]},
		5: {dirs: [[-1,0], [0,-1]],adjs: [[2,3,4], [1,4,6]]},
		6: {dirs: [[-1,0], [0,1]], adjs: [[2,3,4], [1,3,5]]}
	}
	let path = Array.from({length: grid.length}, el => new Uint16Array(grid[0].length))
	let y = 0, x = 0;

	function getNextSegment(segment, y, x) {
		let dir = 0;
		let ny = y + SEGMENTS[segment].dirs[dir][0];
		let nx = x + SEGMENTS[segment].dirs[dir][1];
		if (ny < 0 || ny >= M || nx < 0 || nx >= N || path[ny][nx]) {
			dir = 1;
			ny = y + SEGMENTS[segment].dirs[dir][0];
			nx = x + SEGMENTS[segment].dirs[dir][1];
		}
		return {dir, ny, nx}
	}

	function isValid(y, x) {
		for (let i = 0; i < M*N; i++) {
			if (y == M-1 && x == N-1) return true;
			path[y][x] = i+1;
			let cur = grid[y][x];
			let next = getNextSegment(cur, y, x);
			if (next.ny >= M || next.nx >= N) return false;
			if (!SEGMENTS[cur].adjs[next.dir].includes(grid[next.ny][next.nx])) return false;
			y = next.ny;
			x = next.nx;
		}
		return false
	}

	if (grid[0][0] !== 4) return isValid(y, x);
	path[0][0] = 1;
	return isValid(y, x+1) || isValid(y+1, x);
};
Check if There is a Valid Path in a Grid