在一个n*m二维网格图中,有以下三种地形:“﹟”代表湖泊;“.”代表陆地;?代表陆地与湖泊有可能的未知地形,求是否存在一种或多种在未知地形填充湖泊/陆地的方案,使得最后地上全部的陆地区域组成一个四联通块(陆地四联通是指,在任意一个陆地格子出发,只是任意使用上下左右四个方向操作,可以访问到任何一块其他的陆地)。 无解输出“Impossible”,多解输出“Ambiguous”,唯一解输出一个n*m的网格图,使得之前的“?”均被填充为“﹟”或“.”,且陆地四联通。 输入样例:第一行两个整数n,m代表地形的行、列数。后面一个n行m列的矩阵代表地形。 输出样例:如题意(不含引号)。
时间: 2024-02-13 07:02:17 浏览: 22
以下是Python3代码实现,使用BFS进行搜索,通过记录每个位置的可行性来判断是否有多解或无解的情况:
```python
from collections import deque
n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]
# 记录每个位置是否可能为湖泊或陆地,0表示未确定,1表示为陆地,-1表示为湖泊
status = [[0 for _ in range(m)] for _ in range(n)]
# 初始化已知的湖泊和陆地位置
for i in range(n):
for j in range(m):
if grid[i][j] == '#':
status[i][j] = -1
elif grid[i][j] == '.':
status[i][j] = 1
# 判断是否为四联通块
def is_connected():
visited = [[False for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if status[i][j] == 1:
# 从一个陆地位置开始进行BFS
queue = deque([(i, j)])
visited[i][j] = True
while queue:
x, y = queue.popleft()
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and status[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
# 判断是否所有陆地都连通
for i in range(n):
for j in range(m):
if status[i][j] == 1 and not visited[i][j]:
return False
return True
# BFS搜索
def bfs():
queue = deque()
# 将所有已知的湖泊位置和四联通块的陆地位置加入队列
for i in range(n):
for j in range(m):
if status[i][j] == -1:
queue.append((i, j))
while queue:
x, y = queue.popleft()
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx, ny = x + dx, y + dy
# 如果可以填充为陆地,则将其加入队列
if 0 <= nx < n and 0 <= ny < m and status[nx][ny] == 0:
status[nx][ny] = 1
if is_connected():
queue.append((nx, ny))
else:
status[nx][ny] = 0
# 如果可以填充为湖泊,则将其加入队列
elif 0 <= nx < n and 0 <= ny < m and status[nx][ny] == 0:
status[nx][ny] = -1
if is_connected():
queue.append((nx, ny))
else:
status[nx][ny] = 0
# 开始搜索
bfs()
# 判断是否有多解或无解
has_question = False
for i in range(n):
for j in range(m):
if status[i][j] == 0:
has_question = True
elif status[i][j] == -1 and grid[i][j] == '.':
print('Impossible')
exit()
elif status[i][j] == 1 and grid[i][j] == '#':
print('Impossible')
exit()
if has_question:
print('Ambiguous')
exit()
# 输出最终结果
for i in range(n):
print(''.join('#' if status[i][j] == -1 else '.' for j in range(m)))
```
时间复杂度为$O(nm(m+n))$,其中$m+n$是搜索中每个位置的可能性个数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)