Approach
Breadth-first search
For Find Minimum Time to Reach Last Room II, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 46 lines of Java from the credited upstream file 3342.java.
- The implementation visibly relies on sequence storage, work queue.
- 2 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution {2 3 public int minTimeToReach(int[][] moveTime) {4 return dijkstra(moveTime, new Pair<>(0, 0),5 new Pair<>(moveTime.length - 1, moveTime[0].length - 1));6 }7 8 private int dijkstra(int[][] moveTime, Pair<Integer, Integer> src, Pair<Integer, Integer> dst) {9 final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};10 final int m = moveTime.length;11 final int n = moveTime[0].length;12 int[][] dist = new int[m][n];13 Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));14 15 dist[0][0] = 0;16 Queue<Pair<Integer, Pair<Integer, Integer>>> minHeap =17 new PriorityQueue<>(Comparator.comparingInt(Pair::getKey)) {18 { offer(new Pair<>(dist[0][0], src)); } 19 };20 21 while (!minHeap.isEmpty()) {22 final int d = minHeap.peek().getKey();23 final Pair<Integer, Integer> u = minHeap.poll().getValue();24 if (u.equals(dst))25 return d;26 final int i = u.getKey();27 final int j = u.getValue();28 if (d > dist[i][j])29 continue;30 for (int[] dir : DIRS) {31 final int x = i + dir[0];32 final int y = j + dir[1];33 if (x < 0 || x == m || y < 0 || y == n)34 continue;35 final int newDist = Math.max(moveTime[x][y], d) + ((i + j) % 2 + 1);36 if (newDist < dist[x][y]) {37 dist[x][y] = newDist;38 minHeap.offer(new Pair<>(newDist, new Pair<>(x, y)));39 }40 }41 }42 43 return -1;44 }45}46