Solved!
Difficulty: Div2C

Classic 思考题

HP

You are given a grid of n*m cells. You start from a starting cell S and can move up, down, left or right in one step without leaving the grid. Find: is it possible to visit each cell once and exactly once. Output the path if possible.

Note: the grid does not contain any obstacles.

Examples

n=3, m=3, S=(2,2)
Output: (2,2) -> (2,3) -> (1,3) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)

n=1, m=3, S=(2,1)
Output: impossible

Constraints

For 50%, 1\leq nm\leq 10^5, nm is even.

For 100%, 1\leq nm\leq 10^5

Solution

By Zzzyt and XGN

This is a classic problem but we will state the answer here so you do not need to search it yourself.

If n or m is even, then the grid graph has a Hamilton cycle. The cycle can be constructed by using a snake pattern. As you have a cycle, you can break apart the cycle from S and get a path.

If n and m are both odd, we now show it is sufficient to only consider the case if S is on the edge.

Proof:
If S is not on the edge, then we can partition the grid into two parts. One part will always have even width or height. The part with even width/height can be traversed using the Hamilton cycle and the last cell traversed will still be on the edge (if traversed in the correct direction).

We now show that it is not possible to construct such path if S is not the majority color if the grid is colored using a chessboard pattern of black and white.

Proof:
If S is colored A and the other color is B. A path traversing all cells will have either the same number of A and B cells or the number of A cells is the number of B cells plus 1.

Example:
ABABAB --> A=B
ABABA --> A=B+1

If S is on the edge and is majority colored, the construction is always possible and simple. Just move to one corner and perform zig-zag snake-style movement.