This task is a kind of shortest path problem.

Define a vertex set as the set of grid states, and add an edge from a state \(X\) to a state \(Y\) when the state \(Y\) can be obtained by one operation from state \(X\); then the shortest distance from the initial state to the state without trash is the answer to the problem. Note that the placements of trash determines the grid state, because Takahashi does not move.

But how many vertices can there be? This can be bounded by \(O(H^3W^3)\) by the following discussion:

An arrangement of trash can always be written using integers \(lx, rx, ly, ry, dx, dy\) in the following format:

• Cell \((x + dx, y + dy)\) has trash if \(lx \leq x < rx\), \(ly \leq y < ry\), and cell \((x, y)\) has trash in the initial state.
• No other trash is in the grid.

Here, since \(0 \leq lx, rx \leq H\) and \(-H \leq dx \leq H\), we can bound \(lx, rx\) and \(dx\) by \(O(H)\), and similarly we can bound \(ly, ry\), and \(dy\) by \(O(W)\). Therefore, there are \(O(H^3W^3)\) states.

Since the outdegree of each vertex is \(4\) or less, the computational complexity can be evaluated as \(O(H^3W^3)\), which can be obtained by performing BFS (Breadth-First Search) on this graph.

On implementation, we may manage the shortest distances in an array with \(lx, rx, ly, ry, dx\), and \(dy\) as keys. Storing the actual grid state also seems to run fast enough.

Given \(lx, rx, ly, ry, dx\), and \(dy\), whether trash remains or not can be determined using cumulative sums in \(O(1)\) time, with \(O(HW)\) precalculation. In case of writer’s implementation, even running a double loop worked fast enough.

Sample code