Check if There is a Valid Path in a Grid

Given a m x n grid. Each cell of the 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 which 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.

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).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

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

Solution:

class Solution {
    //                   u  l  r d
    int[] dx = new int[]{-1,0,0,1};
    int[] dy = new int[]{0,-1,1,0};
    
    public boolean hasValidPath(int[][] grid) {
        Map<Integer, List<Integer>> map = new HashMap();
        map.put(1, Arrays.asList(1, 2));
        map.put(2, Arrays.asList(0, 3));
        map.put(3, Arrays.asList(1, 3));
        map.put(4, Arrays.asList(2, 3));
        map.put(5, Arrays.asList(0, 1));
        map.put(6, Arrays.asList(0, 2));
        int m = grid.length, n = grid[0].length;
        Set<Integer> visited = new HashSet();
        Deque<Integer> queue = new ArrayDeque();
        queue.offer(0);
        visited.add(0);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            int x = curr / n, y = curr % n;
            if (x == m - 1 && y == n - 1) {
                return true;
            }
            for (int k : map.get(grid[x][y])) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int s = grid[nx][ny];
                    if (map.get(s).contains(3 - k)) {
                        int next = nx * n + ny;
                        if (visited.add(next)) {
                            queue.offer(next);
                        }
                    }
                }
            }
        }
        return false;
    }
}