The shaded part of the maze is the impassable location. Each position in the maze can explore the feasible path in 8 directions. Assuming that the exit position is at the bottom right corner (6, 8) and the entrance is at the top left corner (1, 1), it is required to design an algorithm to find a path from the entrance to the exit. Maze Problem • Input: The data of Maze,ends with 0 0 • Output: Yes or No. If there is a path from the entrance to the exit, output "Yes". Otherwise, output “No”. 8 10 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 6 8 Yes
时间: 2024-01-02 13:03:04 浏览: 31
Here's a Python solution to the maze problem using breadth-first search algorithm:
```python
from collections import deque
# read in the maze data
maze = []
while True:
row = list(map(int, input().split()))
if row == [0, 0]:
break
maze.append(row)
# set the start and end positions
start = (1, 1)
end = (6, 8)
# define the 8 possible directions
directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
# initialize the visited set and the queue for BFS
visited = set()
queue = deque([start])
# perform BFS
while queue:
current_pos = queue.popleft()
if current_pos == end:
print("Yes")
break
for d in directions:
next_pos = (current_pos[0] + d[0], current_pos[1] + d[1])
if next_pos[0] < 1 or next_pos[0] > len(maze) or next_pos[1] < 1 or next_pos[1] > len(maze[0]):
continue
if maze[next_pos[0]-1][next_pos[1]-1] == 0 or next_pos in visited:
continue
visited.add(next_pos)
queue.append(next_pos)
else:
print("No")
```
The program reads in the maze data from standard input, and then performs breadth-first search from the start position to find a path to the end position. The eight possible directions are defined in the `directions` list, and the visited positions are stored in the `visited` set. If the end position is reached, the program outputs "Yes". If the queue becomes empty and the end position is not reached, the program outputs "No".
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)