LeetCode 2258: Escape the Spreading Fire
Problem Description
Explanation:
- To solve this problem, we can use a Breadth-First Search (BFS) algorithm to simulate the spreading of fire and the movement of the person on the grid.
- We will start by initializing a queue to keep track of cells to visit, a set to store visited cells, and variables to keep track of time and the maximum minutes the person can stay in the initial position.
- We will iteratively process cells in the queue, simulating the spreading of fire and the person's movement.
- At each step, we check if the person can safely reach the safehouse without moving. If so, we update the maximum minutes they can stay.
- We continue the process until either the person reaches the safehouse, cannot move further, or the queue is empty.
- If the person can always reach the safehouse regardless of the minutes stayed, we return 10^9. If it is impossible to reach the safehouse, we return -1.
Time Complexity: O(mn) where m and n are the dimensions of the grid. Space Complexity: O(mn) where m and n are the dimensions of the grid.
:
Solutions
class Solution {
public int escapeTheFire(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new int[]{0, 0, 0});
visited.add("0-0");
int maxMinutes = 0;
while (!queue.isEmpty()) {
int size = queue.size();
boolean reachedSafehouse = false;
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
int minutes = curr[2];
if (x == m - 1 && y == n - 1) {
reachedSafehouse = true;
maxMinutes = Math.max(maxMinutes, minutes);
}
for (int[] dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != 1 && !visited.contains(nx + "-" + ny)) {
if (grid[nx][ny] == 0 || (grid[nx][ny] == 2 && minutes == 0)) {
queue.offer(new int[]{nx, ny, minutes});
visited.add(nx + "-" + ny);
} else if (grid[nx][ny] == 2 && minutes > 0) {
queue.offer(new int[]{nx, ny, minutes - 1});
visited.add(nx + "-" + ny);
}
}
}
}
if (reachedSafehouse) break;
}
return maxMinutes == 0 ? -1 : maxMinutes;
}
}Loading editor...