Description

There is an $m \times n$ grid maze (meaning $m$ rows and $n$ columns), with some cells passable and others not. Use $1$ for passable and $0$ for impassable. The input provides these $m \times n$ values and the start and end points (each point is described by two numbers: its row index and column index). Your task is to write a program to find all feasible paths such that no cell is visited more than once, and movement is allowed only in the four directions: up, down, left, and right. If no path is feasible, output the corresponding information ($-1$ means no path).

Priority order: left, up, right, down. The testdata are guaranteed to be randomly generated.

Input Format

The first line contains two integers $m, n$ ($1 < m, n < 15$). Then follow $m$ rows and $n$ columns of data consisting of $1$ and $0$. The last two lines are the start point and the end point.

Output Format

Output all feasible paths. When describing a point, use the form $(x, y)$. Except for the starting point, connect consecutive points using -> to indicate direction.

If there is no feasible path, output $-1$.

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

Hint

The testdata are guaranteed to be randomly generated. In fact, if $n = m = 14$ and every cell is $1$, there are $69450664761521361664274701548907358996488$ paths.

Translated by ChatGPT 5