Number Connection Puzzle
Time limit5sMemory limit128 MB
Find a Hamiltonian path on an m by n grid (both even, up to 8) connecting two given endpoints, moving only to adjacent cells without crossing itself, or report -1.
- Level
Medium6 of 10
- Topics
- Backtracking, Graph, DFS
- Solved
- No attempts yet
Problem
In a grid of numbers, two cells with the same number must be connected by one line. In this problem, exactly two cells contain the number 1.
The line moves only between horizontally or vertically adjacent cells. It cannot break, branch, or cross itself. The two 1 cells must be the two endpoints of the line, and the line must pass through every cell of the grid exactly once.
The number of rows m and columns n are both even, and 2 ≤ m, n ≤ 8. Given the positions of the two 1 cells, find a path that satisfies these conditions.
Input
The first line contains the number of test cases T.
For each test case, the first line contains the number of rows m and columns n. The next two lines contain the positions (i, j) and (a, b) of the two 1 cells. All coordinates are 1-indexed.
Output
For each test case, print -1 if no valid path exists.
Otherwise, print 1 first, followed by m × n lines containing the coordinates visited by the path in order. The first and last coordinates must be the two given 1 cells.