Java: breadth-first search for a shortest path
State-space search treats a problem as states connected by moves. Breadth-first search explores states in order of their distance from the start, using a first-in, first-out queue. When all moves cost the same, the first time it reaches the goal is a shortest path.
Java
import java.util.*;
class Main {
public static void main(String[] args) {
String[] grid = {
"S.#.",
"..#.",
"...G",
};
int rows = grid.length, cols = grid[0].length();
int[][] dist = new int[rows][cols];
for (int[] row : dist) {
Arrays.fill(row, -1);
}
Deque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {0, 0});
dist[0][0] = 0;
int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] move : moves) {
int r = cell[0] + move[0], c = cell[1] + move[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r].charAt(c) != '#' && dist[r][c] < 0) {
dist[r][c] = dist[cell[0]][cell[1]] + 1;
queue.add(new int[] {r, c});
}
}
}
System.out.println("shortest path to G: " + dist[2][3]);
}
}