714246. Shortest XY distance in Grid
Medium
Shortest XY Distance in Grid
Summary
Given a grid with dimensions m and n, find the shortest distance between two points (x1, y1) and (x2, y2). The distance is measured as the minimum number of steps to reach (x2, y2) from (x1, y1), where each step can be either horizontally or vertically.
Detailed Explanation
To solve this problem, we will use Breadth-First Search (BFS) algorithm. BFS is a traversal algorithm that starts at the root node and visits all nodes in layer-by-layer order. In our case, we start from (x1, y1) and traverse the grid until we reach (x2, y2).
Here's a step-by-step breakdown of the solution:
- Create a queue to store cells to visit.
- Initialize the distance matrix with infinity for all cells except the starting cell
(x1, y1), which is set to 0. - Enqueue the starting cell and mark it as visited.
- While the queue is not empty:
- Dequeue a cell and consider its neighbors (up, down, left, right).
- For each neighbor that has not been visited yet, update the distance matrix with the minimum of its current value and the distance from
(x1, y1)to the dequeued cell plus 1. - Mark the neighbor as visited.
- Return the shortest distance between
(x1, y1)and(x2, y2), which is stored in the distance matrix at position(x2, y2).
Here's an ASCII art diagram of the grid:
0 1 2 ... n-1
0 | x1 | x1+1 | ... | x2
1 | x1-1 | x1 | ... |
...
m-1 | ... | ... | ... | x2
Time complexity: O(m*n) Space complexity: O(m*n)
Optimized Solutions
Java
import java.util.*;
public class ShortestXYDistance {
public static int shortestXY(int[][] grid, int[] start, int[] end) {
int m = grid.length;
int n = grid[0].length;
// Create a distance matrix with infinity for all cells
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
// Set the starting cell to 0
dist[start[0]][start[1]] = 0;
// Create a queue and enqueue the starting cell
Queue<int[]> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] neighbor : getNeighbors(cell, m, n)) {
if (neighbor[0] < 0 || neighbor[0] >= m || neighbor[1] < 0 || neighbor[1] >= n) continue;
if (dist[neighbor[0]][neighbor[1]] <= dist[cell[0]][cell[1]] + 1) continue;
// Update the distance and mark as visited
dist[neighbor[0]][neighbor[1]] = dist[cell[0]][cell[1]] + 1;
queue.add(neighbor);
}
}
return dist[end[0]][end[1]];
}
private static int[][] getNeighbors(int[] cell, int m, int n) {
List<int[]> neighbors = new ArrayList<>();
if (cell[0] > 0) neighbors.add(new int[]{cell[0]-1, cell[1]});
if (cell[0] < m-1) neighbors.add(new int[]{cell[0]+1, cell[1]});
if (cell[1] > 0) neighbors.add(new int[]{cell[0], cell[1]-1});
if (cell[1] < n-1) neighbors.add(new int[]{cell[0], cell[1]+1});
return neighbors.toArray(new int[0][]);
}
}