Minimum Moves to Reach Target with Rotations LeetCode solution in Java

1
class Solution {
2
  public int minimumMoves(int[][] grid) {
3

4
    int n = grid.length;
5
    // boolean[][][][] visited = new boolean[n][n][n][n];
6
    Set<Position> set = new HashSet<>();
7

8
    Queue<Position> q = new LinkedList<>();
9
    q.offer(new Position(0, 0, 0, 1));
10
    int count = 0;
11

12
    if (grid[n - 1][n - 2] == 1 || grid[n - 1][n - 1] == 1) return -1;
13

14
    while (!q.isEmpty()) {
15
      ++count;
16
      Queue<Position> nextq = new LinkedList<>();
17
      while (!q.isEmpty()) {
18

19
        Position p = q.poll();
20

21
        int r1 = p.getr1();
22
        int r2 = p.getr2();
23
        int c1 = p.getc1();
24
        int c2 = p.getc2();
25

26
        if (r1 == n - 1 && r2 == n - 1 && c1 == n - 2 && c2 == n - 1) return count - 1;
27

28
        if (set.contains(p)) continue;
29

30
        if (c1 + 1 < n && grid[r1][c1 + 1] != 1 && c2 + 1 < n && grid[r2][c2 + 1] != 1)
31
          nextq.offer(new Position(r1, c1 + 1, r2, c2 + 1));
32
        if (r1 + 1 < n && grid[r1 + 1][c1] != 1 && r2 + 1 < n && grid[r2 + 1][c2] != 1)
33
          nextq.offer(new Position(r1 + 1, c1, r2 + 1, c2));
34

35
        if (r1 == r2
36
            && r1 + 1 < n
37
            && r2 + 1 < n
38
            && grid[r1 + 1][c1] == 0
39
            && grid[r2 + 1][c2] == 0
40
            && grid[r1 + 1][c1] == 0) nextq.offer(new Position(r1, c1, r1 + 1, c1));
41

42
        if (c1 == c2
43
            && c1 + 1 < n
44
            && c2 + 1 < n
45
            && grid[r1][c1 + 1] == 0
46
            && grid[r2][c1 + 1] == 0
47
            && grid[r1][c1 + 1] == 0) nextq.offer(new Position(r1, c1, r1, c1 + 1));
48
        set.add(p);
49
      }
50
      q = nextq;
51
    }
52
    return -1;
53
  }
54

55
  private class Position {
56
    int r1;
57
    int c1;
58
    int r2;
59
    int c2;
60

61
    public Position(int r1, int c1, int r2, int c2) {
62
      this.r1 = r1;
63
      this.r2 = r2;
64
      this.c1 = c1;
65
      this.c2 = c2;
66
    }
67

68
    public int getr1() {
69
      return this.r1;
70
    }
71

72
    public int getr2() {
73
      return this.r2;
74
    }
75

76
    public int getc1() {
77
      return this.c1;
78
    }
79

80
    public int getc2() {
81
      return this.c2;
82
    }
83

84
    @Override
85
    public int hashCode() {
86
      final int prime = 31;
87
      int result = 1;
88
      result = prime * r1 + c1 + prime * r2 + c2;
89
      return result;
90
    }
91

92
    @Override
93
    public boolean equals(Object obj) {
94
      Position p = (Position) obj;
95
      if (this.r1 == p.getr1()
96
          && this.r2 == p.getr2()
97
          && this.c1 == p.getc1()
98
          && this.c2 == p.getc2()) return true;
99
      else return false;
100
    }
101
  }
102
}