Minimum Moves to Move a Box to Their Target Location LeetCode solution in Java

1
/**
2
 * Finds Initial State (State consists of shopkeeper & box locations + # of boxMoves) Uses BFS/A*
3
 * Algorithm to visit valid transition states Note: The min heuristic here is # of boxMoves +
4
 * manHattanDistance between box & target locations
5
 */
6
class Solution {
7
  private int targetRow;
8
  private int targetCol;
9
  private char[][] grid;
10
  private static int[][] DIRS = {
11
    {1, 0}, // Down
12
    {-1, 0}, // Up
13
    {0, 1}, // Right
14
    {0, -1} // Left
15
  };
16

17
  /** State holds shopkeeper and box location, as well as how many times the box has been pushed */
18
  class State implements Comparable<State> {
19
    int personRow;
20
    int personCol;
21
    int boxRow;
22
    int boxCol;
23
    int boxPushes;
24

25
    public State(int personRow, int personCol, int boxRow, int boxCol, int boxPushes) {
26
      this.personRow = personRow;
27
      this.personCol = personCol;
28
      this.boxRow = boxRow;
29
      this.boxCol = boxCol;
30
      this.boxPushes = boxPushes;
31
    }
32

33
    // Override equals - used along with hashcode when we have visited HashSet
34
    public boolean equals(Object o) {
35
      State other = (State) o;
36
      return this.personRow == other.personRow
37
          && this.personCol == other.personCol
38
          && this.boxRow == other.boxRow
39
          && this.boxCol == other.boxCol;
40
    }
41

42
    // Override the hashCode - Note: it's okay for this to have collisions
43
    // But it won't due to the problem constraint that there is a bound on NxM dimensions
44
    public int hashCode() {
45
      return personRow * 10_000 + personCol * 1_000 + boxRow * 100 + boxCol;
46
    }
47

48
    // Override to string method - helpful in debugging state.
49
    public String toString() {
50
      return "ShopKeeper:{row:"
51
          + personRow
52
          + ", col:"
53
          + personCol
54
          + "}"
55
          + "Box:{row:"
56
          + boxRow
57
          + ", col:"
58
          + boxCol
59
          + "}";
60
    }
61

62
    // Implement comparable interface such that we return the state that
63
    // has the possibility of lowest distance using box push count + Manhattan distance
64
    public int compareTo(State other) {
65
      int minDistanceThis = this.boxPushes + distanceToTarget(this);
66
      int minDistanceOther = other.boxPushes + distanceToTarget(other);
67
      return Integer.compare(minDistanceThis, minDistanceOther);
68
    }
69
  }
70

71
  // Calculates Manhattan distance
72
  private int distanceToTarget(State state) {
73
    int yDiff = Math.abs(state.boxCol - targetCol);
74
    int xDiff = Math.abs(state.boxRow - targetRow);
75
    return yDiff + xDiff;
76
  }
77

78
  /**
79
   * Given a state, compare box location to target location to determine if it is a solution state.
80
   */
81
  private boolean isSolutionState(State state) {
82
    return state.boxRow == targetRow && state.boxCol == targetCol;
83
  }
84

85
  /**
86
   * Given a state, finds all valid transition states. This is accomplished by moving the ShopKeeper
87
   * in all 4 directions and validate - Next ShopKeeper location is in bounds and is not a wall
88
   *
89
   * <p>We have additional logic for when the next shopkeeper location is the box location: - Get
90
   * next box location, by pushing the same direction, again validate that the next box location is
91
   * in bounds, and is not a wall.
92
   *
93
   * <p>If it's a valid transition, create the new state with the new shop keeper location and if
94
   * the box moved, the new box location (also increment the number of box moves).
95
   */
96
  private List<State> getNeighbors(State state) {
97

98
    int personRow = state.personRow;
99
    int personCol = state.personCol;
100
    int boxRow = state.boxRow;
101
    int boxCol = state.boxCol;
102

103
    List<State> states = new ArrayList<>();
104
    for (int[] dir : DIRS) {
105
      int rowMove = dir[0];
106
      int colMove = dir[1];
107
      int personRowNew = personRow + rowMove;
108
      int personColNew = personCol + colMove;
109
      // Shopkeeper cannot move into wall or go out of bounds skip to next direction
110
      if (!inBounds(personRowNew, personColNew) || isWall(personRowNew, personColNew)) {
111
        continue;
112
      }
113
      // Whether or not person will collide with box
114
      boolean willPushBox = personRowNew == boxRow && personColNew == boxCol;
115

116
      if (willPushBox) {
117
        int boxRowNew = boxRow + rowMove;
118
        int boxColNew = boxCol + colMove;
119
        // Validate box can be pushed - if so push box and add to neighbor states
120
        if (inBounds(boxRowNew, boxColNew) && !isWall(boxRowNew, boxColNew)) {
121
          states.add(
122
              new State(personRowNew, personColNew, boxRowNew, boxColNew, state.boxPushes + 1));
123
        }
124
      } else {
125
        // Shop keeper moved, but not box
126
        states.add(new State(personRowNew, personColNew, boxRow, boxCol, state.boxPushes));
127
      }
128
    }
129
    return states;
130
  }
131

132
  // Given row/col, return whether it is wall
133
  private boolean isWall(int row, int col) {
134
    char cell = grid[row][col];
135
    return cell == '#';
136
  }
137

138
  // Given row/col return whether is inBounds
139
  private boolean inBounds(int row, int col) {
140
    int rows = grid.length;
141
    int cols = grid[0].length;
142
    if (row < 0 || col < 0 || row > rows - 1 || col > cols - 1) {
143
      return false;
144
    }
145
    return true;
146
  }
147

148
  /** Returns initial state. Also finds and stores the target location. */
149
  private State getInitialState() {
150

151
    int shopKeeperRow = 0;
152
    int shopKeeperCol = 0;
153

154
    int boxRow = 0;
155
    int boxCol = 0;
156

157
    for (int r = 0; r < grid.length; r++) {
158
      char[] row = grid[r];
159
      for (int c = 0; c < row.length; c++) {
160
        char cell = grid[r][c];
161
        if (cell == 'T') {
162
          this.targetRow = r;
163
          this.targetCol = c;
164
        } else if (cell == 'B') {
165
          boxRow = r;
166
          boxCol = c;
167
        } else if (cell == 'S') {
168
          shopKeeperRow = r;
169
          shopKeeperCol = c;
170
        }
171
      }
172
    }
173

174
    return new State(shopKeeperRow, shopKeeperCol, boxRow, boxCol, 0);
175
  }
176

177
  public int minPushBox(char[][] grid) {
178
    this.grid = grid;
179

180
    State initialState = getInitialState();
181
    Queue<State> queue = new PriorityQueue<>();
182
    Set<State> visited = new HashSet<>();
183
    queue.offer(initialState);
184

185
    // Explore every state using BSF and keep track of the best solution
186
    while (!queue.isEmpty()) {
187
      State state = queue.poll();
188
      if (visited.contains(state)) {
189
        continue;
190
      }
191
      visited.add(state);
192
      /*
193
        Note: the reason we can return the first solution state we find, is because we are
194
        using priority queue with minDistance heuristic which means the first solution we find
195
        is guaranteed to be the optimal solution - (A* Algorithm)
196
      */
197
      if (isSolutionState(state)) {
198
        return state.boxPushes;
199
      }
200
      for (State neighbor : getNeighbors(state)) {
201
        if (!visited.contains(neighbor)) {
202
          queue.offer(neighbor);
203
        }
204
      }
205
      ;
206
    }
207
    // No solution - return -1
208
    return -1;
209
  }
210
}