Maze Shortest Path

Problem Description

Define a two-dimensional array:

int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};

It represents a maze, where 1 is a wall and 0 is a free cell. You may only move horizontally or vertically, not diagonally. Write a program that finds the shortest route from the upper-left corner to the lower-right corner.

Input Format

A $5 \times 5$ two-dimensional array representing the maze. The data guarantees a unique solution.

Output Format

The shortest path from the upper-left to the lower-right corner, in the format shown in the sample.

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

Limitation

1 s, 1024 KiB for each test case.