Approach
Breadth-first search
For Minimum Time Takes to Reach Destination Without Drowning, 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
- 75 lines of Java from the credited upstream file 2814.java.
- The implementation visibly relies on sequence storage, work queue.
- 10 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 public int minimumSeconds(List<List<String>> land) {3 final int m = land.size();4 final int n = land.get(0).size();5 final int[][] floodDist = getFloodDist(land);6 Queue<Pair<Integer, Integer>> q = new LinkedList<>();7 boolean[][] seen = new boolean[m][n];8 9 for (int i = 0; i < m; ++i)10 for (int j = 0; j < n; ++j)11 if (land.get(i).get(j).equals("S")) {12 q.offer(new Pair<>(i, j));13 seen[i][j] = true;14 }15 16 for (int step = 1; !q.isEmpty(); ++step)17 for (int sz = q.size(); sz > 0; --sz) {18 final int i = q.peek().getKey();19 final int j = q.poll().getValue();20 for (int[] dir : DIRS) {21 final int x = i + dir[0];22 final int y = j + dir[1];23 if (x < 0 || x == m || y < 0 || y == n)24 continue;25 if (land.get(x).get(y).equals("D"))26 return step;27 if (floodDist[x][y] <= step || land.get(x).get(y).equals("X") || seen[x][y])28 continue;29 q.offer(new Pair<>(x, y));30 seen[x][y] = true;31 }32 }33 34 return -1;35 }36 37 private final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};38 39 private int[][] getFloodDist(List<List<String>> land) {40 final int m = land.size();41 final int n = land.get(0).size();42 int[][] dist = new int[m][n];43 Queue<Pair<Integer, Integer>> q = new LinkedList<>();44 boolean[][] seen = new boolean[m][n];45 46 Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));47 48 for (int i = 0; i < m; ++i)49 for (int j = 0; j < n; ++j)50 if (land.get(i).get(j).equals("*")) {51 q.offer(new Pair<>(i, j));52 seen[i][j] = true;53 }54 55 for (int d = 0; !q.isEmpty(); ++d)56 for (int sz = q.size(); sz > 0; --sz) {57 final int i = q.peek().getKey();58 final int j = q.poll().getValue();59 dist[i][j] = d;60 for (int[] dir : DIRS) {61 final int x = i + dir[0];62 final int y = j + dir[1];63 if (x < 0 || x == m || y < 0 || y == n)64 continue;65 if (land.get(x).get(y).equals("X") || land.get(x).get(y).equals("D") || seen[x][y])66 continue;67 q.offer(new Pair<>(x, y));68 seen[x][y] = true;69 }70 }71 72 return dist;73 }74}75