Card 03/ 08
The Grid Search Template in Python, Java and TypeScript
A queue of cells, four directions, a bounds check and a distance grid that doubles as the visited mark.
The grid search template is a breadth-first search over cells: a queue of (row, column) pairs, the four offsets as a constant, a bounds check before the grid is read, and a distance grid where −1 means not yet reached, so no separate visited set is needed. A cell is marked by writing its distance as it enters the queue. The highlighted lines are the ones that change between problems: the test for a passable cell and what is recorded when a cell is reached. Each listing runs on the grid S . # . / . . . . / # . # T, from (0, 0).
The grid search template in three languages
from collections import deque
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
def distances_from(grid: list[str], start: tuple[int, int]) -> list[list[int]]:
rows, cols = len(grid), len(grid[0])
distance = [[-1] * cols for _ in range(rows)]
distance[start[0]][start[1]] = 0
queue = deque([start])
while queue:
row, col = queue.popleft()
for d_row, d_col in DIRECTIONS:
r, c = row + d_row, col + d_col
if 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#" and distance[r][c] == -1:
distance[r][c] = distance[row][col] + 1
queue.append((r, c))
return distance
grid = ["S.#.", "....", "#.#T"]
distance = distances_from(grid, (0, 0))
for r, line in enumerate(grid):
print(" ".join("#" if cell == "#" else "." if distance[r][c] == -1 else str(distance[r][c]) for c, cell in enumerate(line)))
print("target (2, 3) is", distance[2][3], "moves away")0 1 # 5
1 2 3 4
# 3 # 5
target (2, 3) is 5 moves awayimport java.util.ArrayDeque;
import java.util.Arrays;
public class GridSearch {
static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int[][] distancesFrom(String[] grid, int startRow, int startCol) {
int rows = grid.length;
int cols = grid[0].length();
int[][] distance = new int[rows][cols];
for (int[] row : distance) {
Arrays.fill(row, -1);
}
distance[startRow][startCol] = 0;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {startRow, startCol});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] direction : DIRECTIONS) {
int r = cell[0] + direction[0];
int c = cell[1] + direction[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r].charAt(c) != '#' && distance[r][c] == -1) {
distance[r][c] = distance[cell[0]][cell[1]] + 1;
queue.add(new int[] {r, c});
}
}
}
return distance;
}
public static void main(String[] args) {
String[] grid = {"S.#.", "....", "#.#T"};
int[][] distance = distancesFrom(grid, 0, 0);
for (int r = 0; r < grid.length; r++) {
StringBuilder line = new StringBuilder();
for (int c = 0; c < grid[r].length(); c++) {
char cell = grid[r].charAt(c);
String shown = cell == '#' ? "#" : distance[r][c] == -1 ? "." : String.valueOf(distance[r][c]);
line.append(c == 0 ? "" : " ").append(shown);
}
System.out.println(line);
}
System.out.println("target (2, 3) is " + distance[2][3] + " moves away");
}
}0 1 # 5
1 2 3 4
# 3 # 5
target (2, 3) is 5 moves awayconst DIRECTIONS: ReadonlyArray<readonly [number, number]> = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function distancesFrom(grid: string[], start: [number, number]): number[][] {
const rows = grid.length;
const cols = grid[0].length;
const distance = Array.from({ length: rows }, () => new Array<number>(cols).fill(-1));
distance[start[0]][start[1]] = 0;
const queue: Array<[number, number]> = [start];
let head = 0;
while (head < queue.length) {
const [row, col] = queue[head++];
for (const [dRow, dCol] of DIRECTIONS) {
const r = row + dRow;
const c = col + dCol;
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] !== "#" && distance[r][c] === -1) {
distance[r][c] = distance[row][col] + 1;
queue.push([r, c]);
}
}
}
return distance;
}
const grid = ["S.#.", "....", "#.#T"];
const distance = distancesFrom(grid, [0, 0]);
grid.forEach((line, r) => {
console.log([...line].map((cell, c) => (cell === "#" ? "#" : distance[r][c] === -1 ? "." : String(distance[r][c]))).join(" "));
});
console.log(`target (2, 3) is ${distance[2][3]} moves away`);0 1 # 5
1 2 3 4
# 3 # 5
target (2, 3) is 5 moves awayThe bounds check comes first in each condition, so the grid is never read outside its edges. Python builds the distance grid with a comprehension, because [[-1] * cols] * rows would repeat one list rows times, and writing to one row would write to all of them. Java fills each row of an int array with Arrays.fill and reads a cell with charAt. TypeScript keeps its queue as an array with a head index, because shift() moves every remaining element and would make each dequeue O(n). Each version is O(R · C) time and space.
← → move through sections and cards