Skip to content

2814. Minimum Time Takes to Reach Destination Without Drowning 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
 public:
  int minimumSeconds(vector<vector<string>>& land) {
    const int m = land.size();
    const int n = land[0].size();
    const vector<vector<int>> floodDist = getFloodDist(land);
    queue<pair<int, int>> q;
    vector<vector<bool>> seen(m, vector<bool>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (land[i][j] == "S") {
          q.emplace(i, j);
          seen[i][j] = true;
        }

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : kDirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (land[x][y] == "D")
            return step;
          if (floodDist[x][y] <= step || land[x][y] == "X" || seen[x][y])
            continue;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }

    return -1;
  }

 private:
  static constexpr int kDirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  vector<vector<int>> getFloodDist(const vector<vector<string>>& land) {
    const int m = land.size();
    const int n = land[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    queue<pair<int, int>> q;
    vector<vector<bool>> seen(m, vector<bool>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (land[i][j] == "*") {
          q.emplace(i, j);
          seen[i][j] = true;
        }

    for (int d = 0; !q.empty(); ++d)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        dist[i][j] = d;
        for (const auto& [dx, dy] : kDirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (land[x][y] == "X" || land[x][y] == "D" || seen[x][y])
            continue;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }

    return dist;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
  public int minimumSeconds(List<List<String>> land) {
    final int m = land.size();
    final int n = land.get(0).size();
    final int[][] floodDist = getFloodDist(land);
    Queue<Pair<Integer, Integer>> q = new LinkedList<>();
    boolean[][] seen = new boolean[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (land.get(i).get(j).equals("S")) {
          q.offer(new Pair<>(i, j));
          seen[i][j] = true;
        }

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().getKey();
        final int j = q.poll().getValue();
        for (int[] dir : DIRS) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (land.get(x).get(y).equals("D"))
            return step;
          if (floodDist[x][y] <= step || land.get(x).get(y).equals("X") || seen[x][y])
            continue;
          q.offer(new Pair<>(x, y));
          seen[x][y] = true;
        }
      }

    return -1;
  }

  private final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private int[][] getFloodDist(List<List<String>> land) {
    final int m = land.size();
    final int n = land.get(0).size();
    int[][] dist = new int[m][n];
    Queue<Pair<Integer, Integer>> q = new LinkedList<>();
    boolean[][] seen = new boolean[m][n];

    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (land.get(i).get(j).equals("*")) {
          q.offer(new Pair<>(i, j));
          seen[i][j] = true;
        }

    for (int d = 0; !q.isEmpty(); ++d)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().getKey();
        final int j = q.poll().getValue();
        dist[i][j] = d;
        for (int[] dir : DIRS) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (land.get(x).get(y).equals("X") || land.get(x).get(y).equals("D") || seen[x][y])
            continue;
          q.offer(new Pair<>(x, y));
          seen[x][y] = true;
        }
      }

    return dist;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution:
  def minimumSeconds(self, land: list[list[str]]) -> int:
    self.DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(land)
    n = len(land[0])
    floodDist = self._getFloodDist(land)
    startPos = self._getStartPos(land, 'S')

    q = collections.deque([startPos])
    seen = {startPos}

    step = 1
    while q:
      for _ in range(len(q)):
        i, j = q.popleft()
        for dx, dy in self.DIRS:
          x = i + dx
          y = j + dy
          if x < 0 or x == m or y < 0 or y == n:
            continue
          if land[x][y] == 'D':
            return step
          if floodDist[x][y] <= step or land[x][y] == 'X' or (x, y) in seen:
            continue
          q.append((x, y))
          seen.add((x, y))
      step += 1

    return -1

  def _getFloodDist(self, land: list[list[str]]) -> list[list[int]]:
    m = len(land)
    n = len(land[0])
    dist = [[math.inf] * n for _ in range(m)]
    q = collections.deque()
    seen = set()

    for i, row in enumerate(land):
      for j, cell in enumerate(row):
        if cell == '*':
          q.append((i, j))
          seen.add((i, j))

    d = 0
    while q:
      for _ in range(len(q)):
        i, j = q.popleft()
        dist[i][j] = d
        for dx, dy in self.DIRS:
          x = i + dx
          y = j + dy
          if x < 0 or x == m or y < 0 or y == n:
            continue
          if land[x][y] in 'XD' or (x, y) in seen:
            continue
          q.append((x, y))
          seen.add((x, y))
      d += 1

    return dist

  def _getStartPos(self, land: list[list[str]], c: str) -> tuple[int, int]:
    for i, row in enumerate(land):
      for j, cell in enumerate(row):
        if cell == c:
          return i, j