Marking a Cell Visited When It Leaves the Queue

Marked only when it is taken out, a cell can be queued once by each neighbour: the answer stays right and the queue grows with the edges.

A breadth-first search over a grid must mark a cell visited when it enters the queue, not when it leaves, or a cell can be added once by each of its neighbours. The mistake feels harmless because the distances still come out right: the version below skips a cell that is taken out a second time, so its answer is correct, and only its cost shows. Both versions search an open grid of 3 rows and 5 columns from its centre, (1, 2), and count how many times each cell was added to the queue.

The first listing marks a cell when it is taken out; the second marks it when it is added.

Marking on the way out against marking on the way in

mark_on_exit.pypy

from collections import deque

DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
rows, cols = 3, 5
start = (1, 2)
distance = [[-1] * cols for _ in range(rows)]
added = [[0] * cols for _ in range(rows)]
queue = deque([(start, 0)])
added[1][2] = 1
while queue:
    (row, col), d = queue.popleft()
    if distance[row][col] != -1:
        continue
    distance[row][col] = d
    for d_row, d_col in DIRECTIONS:
        r, c = row + d_row, col + d_col
        if 0 <= r < rows and 0 <= c < cols and distance[r][c] == -1:
            added[r][c] += 1
            queue.append(((r, c), d + 1))

print("entries added:", sum(map(sum, added)))
for line in added:
    print(" ".join(map(str, line)))
print("distances:", " / ".join(" ".join(map(str, line)) for line in distance))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

entries added: 23
2 2 1 2 2
1 1 1 1 1
2 2 1 2 2
distances: 3 2 1 2 3 / 2 1 0 1 2 / 3 2 1 2 3

mark_on_entry.pypy

from collections import deque

DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
rows, cols = 3, 5
start = (1, 2)
distance = [[-1] * cols for _ in range(rows)]
added = [[0] * cols for _ in range(rows)]
queue = deque([start])
distance[1][2] = 0
added[1][2] = 1
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 distance[r][c] == -1:
            distance[r][c] = distance[row][col] + 1
            added[r][c] += 1
            queue.append((r, c))

print("entries added:", sum(map(sum, added)))
for line in added:
    print(" ".join(map(str, line)))
print("distances:", " / ".join(" ".join(map(str, line)) for line in distance))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

entries added: 15
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
distances: 3 2 1 2 3 / 2 1 0 1 2 / 3 2 1 2 3

Both print the same distances. Marking on the way out adds 23 entries for 15 cells: one for each of the grid's 22 edges, since whichever end of an edge is taken out first adds the other, plus the start. The corner-side cells were added twice, once by each neighbour that reached them in the same wave. On a grid that is at most four entries a cell, but on a graph with many edges per vertex the queue grows with the edges rather than the vertices. The rule: mark a cell the moment it is added to the queue, which is also the moment its distance is known.

← → move through sections and cards