Check if There is a Valid Path in a Grid LeetCode solution in Java

1
class Solution {
2
  public boolean hasValidPath(int[][] grid) {
3
    int m = grid.length, n = grid[0].length;
4
    int[][] visited = new int[m][n];
5
    return dfs(grid, 0, 0, m, n, visited);
6
  }
7

8
  public boolean dfs(int[][] grid, int i, int j, int m, int n, int[][] visited) {
9
    if (i == m - 1 && j == n - 1) return true;
10
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] == 1) return false;
11
    visited[i][j] = 1;
12
    if (grid[i][j] == 1) {
13
      if ((j > 0
14
              && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)
15
              && dfs(grid, i, j - 1, m, n, visited))
16
          || (j < n - 1
17
              && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)
18
              && dfs(grid, i, j + 1, m, n, visited))) return true;
19
    } else if (grid[i][j] == 2) {
20
      if ((i < m - 1
21
              && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)
22
              && dfs(grid, i + 1, j, m, n, visited))
23
          || (i > 0
24
              && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)
25
              && dfs(grid, i - 1, j, m, n, visited))) return true;
26
    } else if (grid[i][j] == 3) {
27
      if ((j > 0
28
              && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)
29
              && dfs(grid, i, j - 1, m, n, visited))
30
          || (i < m - 1
31
              && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)
32
              && dfs(grid, i + 1, j, m, n, visited))) return true;
33
    } else if (grid[i][j] == 4) {
34
      if (((i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6))
35
              && dfs(grid, i + 1, j, m, n, visited))
36
          || (j < n - 1
37
              && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)
38
              && dfs(grid, i, j + 1, m, n, visited))) return true;
39
    } else if (grid[i][j] == 5) {
40
      if ((j > 0
41
              && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)
42
              && dfs(grid, i, j - 1, m, n, visited))
43
          || (i > 0
44
              && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)
45
              && dfs(grid, i - 1, j, m, n, visited))) return true;
46
    } else {
47
      if ((i > 0
48
              && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)
49
              && dfs(grid, i - 1, j, m, n, visited))
50
          || (j < n - 1
51
              && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)
52
              && dfs(grid, i, j + 1, m, n, visited))) return true;
53
    }
54
    return false;
55
  }
56
}