Minimum Cost to Make at Least One Valid Path in a Grid LeetCode solution in Java

1
class Solution {
2

3
  int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
4

5
  private boolean isValid(int i, int j, int n, int m) {
6
    return i < n && j < m && i >= 0 && j >= 0;
7
  }
8

9
  private boolean isValidDirection(int[][] grid, int[] currEle, int nx, int ny) {
10
    int nextX = currEle[0], nextY = currEle[1];
11
    int n = grid.length, m = grid[0].length;
12

13
    switch (grid[currEle[0]][currEle[1]]) {
14
      case 1:
15
        nextY++;
16
        break;
17
      case 2:
18
        nextY--;
19
        break;
20
      case 3:
21
        nextX++;
22
        break;
23
      case 4:
24
        nextX--;
25
        break;
26
    }
27

28
    return nextX == nx && nextY == ny;
29
  }
30

31
  public int minCost(int[][] grid) {
32

33
    int n = grid.length;
34
    int m = grid[0].length;
35

36
    int dist[][] = new int[n][m];
37
    boolean vis[][] = new boolean[n][m];
38

39
    LinkedList<int[]> queue = new LinkedList<>(); // for performing 01 BFS
40

41
    for (int i = 0; i < n; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
42

43
    queue.add(new int[] {0, 0});
44
    dist[0][0] = 0;
45

46
    while (!queue.isEmpty()) {
47

48
      int[] currEle = queue.remove();
49
      vis[currEle[0]][currEle[1]] = true;
50

51
      for (int[] currDir : dirs) {
52

53
        int nx = currDir[0] + currEle[0];
54
        int ny = currDir[1] + currEle[1];
55
        if (isValid(nx, ny, n, m) && vis[nx][ny] == false) {
56

57
          if (isValidDirection(grid, currEle, nx, ny)) {
58
            dist[nx][ny] = Math.min(dist[nx][ny], dist[currEle[0]][currEle[1]]);
59
            queue.add(0, new int[] {nx, ny});
60
          } else {
61
            dist[nx][ny] = Math.min(dist[nx][ny], 1 + dist[currEle[0]][currEle[1]]);
62
            queue.add(new int[] {nx, ny});
63
          }
64
        }
65
      }
66
    }
67

68
    return dist[n - 1][m - 1];
69
  }
70
}