LeetCode 1730: Shortest Path to Get Food
Problem Description
Explanation:
-
Algorithmic Idea:
- Use Breadth First Search (BFS) to find the shortest path to reach the food.
- Start the search from the position of the 'S' character (starting point).
- Explore all possible directions (up, down, left, right) from the current position.
- Keep track of the steps taken to reach each cell and update the minimum steps whenever the food ('*') cell is reached.
- Return the minimum steps if the food is reachable, otherwise return -1.
-
Step-by-Step Iteration:
- Start BFS from the starting position 'S'.
- Explore all possible directions from the current position.
- Keep track of the minimum steps needed to reach the food.
- Continue exploring until the food is reached or no valid paths left.
-
Time Complexity: O(N), where N is the total number of cells in the grid.
-
Space Complexity: O(N) for the queue and visited set.
:
Solutions
class Solution {
public int getFood(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 'S') {
queue.offer(new int[]{i, j, 0});
visited.add(i + "," + j);
}
}
}
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
int steps = curr[2];
if (grid[x][y] == '*') {
return steps;
}
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] != 'X' && !visited.contains(newX + "," + newY)) {
queue.offer(new int[]{newX, newY, steps + 1});
visited.add(newX + "," + newY);
}
}
}
return -1;
}
}Loading editor...