-->
当前位置:首页 > 题库

PROGRAMMING:Maze to find the way

Luz5年前 (2021-05-10)题库399
Given a maze of M rows and N columns, where "0" means passable, and "1" means obstacle and impassable. In the maze, it is only allowed to walk in the horizontal or up and down four directions, and the walking position cannot be repeated.
The maze of 5 rows and 8 columns is as follows:
```
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
```
Then the shortest path from the upper left corner (1,1) to the lower right corner (5,8) is as follows:
1,1--》2,1--》2,2--》2,3--》3,3--》3,4--》3,5--》4,5--》5,5--》5,6--》5,7--》5,8
The topic ensures that each maze has at most one shortest path.
Please output the shortest path, if there is no path, then output "no found"
###Input format:
In the first row, enter m and N values to represent the number of rows and columns in the maze.
Then enter the M-line value, where 0 is the path and 1 is the obstacle. The values in each column are separated by a space character.
Next, multiple sets of maze data may be entered.
The input ends when the value of input m is - 1.
###Output format:
Output the number of rows and columns at each position of the path in row order, such as X, y
If there is no path, output "no found"
The results of each group were separated by newline.
###Input example:
Here's a set of mazes. For example:
```in
8 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4
0 0 1 0
0 0 0 0
0 0 1 1
0 1 0 0
-1 -1
```
###Output example:
The corresponding output is given here. For example:
```out
1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8
NO FOUND
```







answer:If there is no answer, please comment