PROBLEM LINK:
Author: Prateek Gupta
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
SIMPLE
PREREQUISITES:
Hamiltonian Path, Hamiltonian Cycle
PROBLEM:
Given an NxM maze, find out if there is a path starting at some cell (a,b), passing through all the cells of the maze and then ends in a cell (c,d) which is adjacent to the starting cell (i.e. they have a border in common). Along the path one can move from the current cell only in one of the 4 directions (up, down, left, right).
QUICK EXPLANATION:
Since the ending cell must be adjacent to the starting cell, the found path can be immediately extended one more step, into a cycle which passes through all the cells of the maze. Such a cycle is called a Hamiltonian cycle. Note that in this case it doesn’t matter which is the starting cell.
An NxM maze has a Hamiltonian cycle if and only if:
- min{N,M}=1 and max{N,M}=2, OR
- min{N,M}>=2 and at least one of N and M is even.
EXPLANATION:
If N=1 or M=1, and max{N,M}>=3 it is obvious that no Hamiltonian cycle exists in the maze (because the cells at the endpoints only have one neighbor). However, a solution does exist when min{N,M}=1 and max{N,M}=2 (the two cells are adjacent to each other).
Let’s now consider the case min{N,M}>=2 and at least one of N or M is even. Let’s assume now that N is even (if it’s not then M must be even, so we just swap the values of N and M between them). We can start the cycle at the cell (1,1), then move right to (1,M). From there we move down to (2,M) and then left to (2,2). From (2,2) we move down to (3,2), right to (3,M), then down to (4,M) and left to (4,2). We continue this procedure until we reach the cell (N,2). From here we move left to (N,1) and then all the way up to (1,1).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.