713140. Shortest Prime Path
Medium
Shortest Prime Path
Summary
The Shortest Prime Path problem involves finding the shortest path in a grid from a given starting point to a target point, where each cell contains a prime number. The algorithm should be efficient and able to handle large grids.
Detailed Explanation
To solve this problem, we can use Breadth-First Search (BFS) with some modifications to accommodate the prime numbers constraint. Here's a step-by-step breakdown of the solution:
- Initialize a queue with the starting point (x1, y1).
- Mark the starting point as visited.
- Repeat the following steps until the queue is empty:
- Dequeue the next cell (x, y) and check if it's the target point. If so, return the distance traveled so far (i.e., the number of cells in the path).
- For each neighboring cell (x', y') that has not been visited yet, check if its value is a prime number.
- If it is, mark it as visited and enqueue it along with its distance from the starting point.
- If the queue becomes empty without finding the target point, return -1 to indicate that there's no path.
To determine whether a number is prime, we can use the following helper function:
function isPrime(n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
The time complexity of this algorithm is O(mn + k), where m and n are the dimensions of the grid, and k is the number of prime numbers in the path. The space complexity is O(mn), as we need to store the visited cells.
Optimized Solutions
Java
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPrimePath {
public int shortestPrimePath(int[][] grid, int x1, int y1, int x2, int y2) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x1, y1});
visited[x1][y1] = true;
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
if (cell[0] == x2 && cell[1] == y2) return distance;
for (int dx : {-1, 0, 1}) {
for (int dy : {-1, 0, 1}) {
int nx = cell[0] + dx;
int ny = cell[1] + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && isPrime(grid[nx][ny])) {
queue.add(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
distance++;
}
return -1;
}
private boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
}