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 indicates a wall and 0 indicates a passable path. Movement is restricted to horizontal or vertical directions (no diagonal movement). The task is to write a program that finds the shortest route from the top-left corner to the bottom-right corner.

Input Format

A 5 × 5 two-dimensional array representing a maze. The data guarantees a unique solution.

Output Format

The shortest path from the top-left corner to the bottom-right corner, formatted as shown in the sample.

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,
};

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