Crossing the mudflats

A crossing guide takes walkers over an estuary at low tide. The bay is surveyed into a square grid, and only some squares hold weight.

The problem

The survey is a square grid of side n. A square holds 0 if it is firm enough to stand on and 1 if it is soft. The walk starts at the top-left square, (0, 0), and finishes at the bottom-right, (n - 1, n - 1).

From a firm square the guide steps to any of the eight touching squares, diagonals included, provided it is inside the grid and firm. Soft squares are never entered, and neither end is exempt: a soft start or a soft finish means no crossing.

Report the length of the shortest crossing as the number of squares stood on, start and finish included, or -1 if no crossing exists.

Input. flats — a list of n lists of n integers, each 0 or 1.

Output. The number of squares on a shortest crossing, or -1.

Example.

flats = [[0, 1],
         [1, 0]]   ->  2

Both off-diagonal squares are soft, but one diagonal move crosses the grid: two squares are stood on, so the answer is 2. A four-direction walker reports -1.

A second example, where the diagonal saves a square:

flats = [[0, 0, 0],
         [1, 1, 0],
         [1, 1, 0]]   ->  4

(0,0), (0,1), diagonally to (1,2), then (2,2). Running along the top row to (0,2) first also crosses, at five squares.

Constraints.

• 1 <= n <= 300, so at most 90,000 squares
• every entry is 0 or 1
• n = 1 is allowed; a single firm square answers 1

Hints

Approach

Brute force

Walk every route that never revisits a square and keep the shortest. Each square offers up to seven onward steps, so the count grows like 7^(n²): a clear 8×8 grid already holds more than 10^11 such routes, and n = 300 is far past any enumeration.

The insight

Every step costs one square, so the frontier of a breadth-first search sweeps outward in exact distance order and the first arrival at the corner is a shortest crossing.

The precondition is uniform edge cost: with every step equal, a queue suffices and no priority ordering is needed. A square never needs revisiting either — the first arrival is already its minimum distance.

Algorithm

1. If the start square is soft, return -1.
2. Mark the start seen and push (0, 0, 1) onto a queue: one square stood on.
3. Pop the front. If it is the bottom-right square, return its count.
4. For each of the eight offsets, if the neighbour is inside the grid, firm and unseen, mark it seen and push it with the count plus one.
5. If the queue empties, return -1.

Complexity

Time O(n²) — each square is pushed at most once and inspects eight neighbours. Space O(n²) for the seen grid and a queue that can hold a whole frontier.

Solution

"""Crossing the mudflats — eight-way breadth-first search on a square grid."""

from collections import deque

MOVES = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))


def solve(flats):
    n = len(flats)
    if flats[0][0] == 1:
        return -1
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True                      # marked on push, never on pop, so no
    queue = deque([(0, 0, 1)])             # cell can enter the queue twice
    while queue:
        r, c, cells = queue.popleft()
        # BFS pops in non-decreasing distance, so the first arrival is shortest.
        if r == n - 1 and c == n - 1:
            return cells
        for dr, dc in MOVES:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and flats[nr][nc] == 0:
                seen[nr][nc] = True
                queue.append((nr, nc, cells + 1))
    return -1

TESTS = [
    (([[0, 1],
       [1, 0]],), 2),
    (([[0, 0, 0],
       [1, 1, 0],
       [1, 1, 0]],), 4),
    (([[1, 0, 0],
       [0, 0, 0],
       [0, 0, 0]],), -1),
    (([[0]],), 1),
    (([[0, 0],
       [0, 1]],), -1),
    (([[0, 0, 0, 0],
       [1, 1, 1, 1],
       [0, 0, 0, 0],
       [0, 0, 0, 0]],), -1),
    (([[0, 0, 0, 0],
       [0, 1, 1, 0],
       [0, 1, 1, 0],
       [0, 0, 0, 0]],), 6),
]

Pitfalls

• Marking a square seen when it is popped instead of when it is pushed. On an open grid the same square is queued once per neighbour that reaches it: the queue swells toward 8n² entries and the run slows by an order of magnitude, though the answer stays right.
• Forgetting the two end squares. With [[1, 0, 0], [0, 0, 0], [0, 0, 0]] the start is soft; a search that pushes (0, 0) unchecked returns 3, not -1.
• Counting moves rather than squares. The answer for [[0]] is 1, not 0 — the guide stands on one square, and every count starts at 1.

Variants

• Lichen on the north wall — the same grid-as-graph reading, four-connected, asking about shape rather than distance.
• Blue mould on the bench — the same grid search started from every source at once, counting the rounds it takes.