The Cleaner That Turns at a Wall
An r by c grid holds free squares (.) and walls (#). A cleaner starts
on a free square at row sr, column sc, facing NORTH, where north is row minus
one. It then performs EXACTLY k actions, and one action is:
if the square directly ahead is inside the grid and free:
move into it that is the action
otherwise:
turn a quarter turn clockwise that is the action
Print how many distinct free squares the cleaner has occupied, counting the one it started on, followed by its final row and column.
3 by 3 empty grid, start 1 1, k = 10 -> 7 2 0
## What most people try first
Treating a turn as free, so that the cleaner turns and then moves within the same action. That halves the number of actions a turn costs and the answer drifts apart from the specification almost immediately. The statement is explicit: a turn IS an action, and a cleaner facing a wall in a one-square dead end spends four actions turning in a full circle and never moves.
The other instinct is to stop early, once every reachable square has been
visited. The specification does not say that. It says exactly k actions, and
the final position is part of the answer, so the cleaner has to keep going even
when it has nothing left to clean.
## Why the count and the position are both asked for
The visit count alone would let a wrong turn direction pass, because an
anticlockwise cleaner often covers the same set of squares as a clockwise one on
a symmetric grid. The final position pins the direction of the turn, and the
sequence of turns and moves that led there. Clockwise in grid coordinates takes
north to east, so the heading (dr, dc) becomes (dc, -dr): (-1,0) becomes
(0,1). Getting that backwards is the single most common defect here, and the
declared tests include grids where it changes the answer.
## Counting distinct squares
A visited grid of booleans with a running total. Increment the total only when
a square is marked for the first time, because the cleaner revisits squares
constantly:
visited[start] = true, total = 1
after each successful move:
if not visited[new square]: visited[new square] = true; total = total + 1
A set of pairs works too, and k reaches 1000000, so the per-action cost has to
be constant either way.
## Cost
O(r c + k): one pass to read the grid, then constant work per action. The
grid of visited flags is O(r c) memory.