题目背景: 一片𝑚×𝑛大小的区域由马路与建筑构成,𝑧 盏坐标分别在(𝑥_𝑖,𝑦_𝑖 )的路灯会照亮距离 其 1 个单位的十字区域,建筑会阻挡灯光的传播,因此需要聪明的你帮忙计算灯光照亮的 区域。 题目描述: 给出区域以及区域中灯和建筑所在的坐标,返回能够被灯照亮的地方。注意,区域左上 角坐标为 (0,0)。输入输出均以矩阵(二维列表)形式表示。 输入格式: 输入共 𝑛 + 𝑧 + 1 行。 第一行包括三个以空格分隔的整数 𝑚,𝑛,𝑧; 第二行到第 𝑧+1 行,每行两个整数 𝑥𝑖,𝑦𝑖,代表第 𝑖 个路灯的位置,𝑖=1,2, ......,𝑧; 第 𝑧 + 2 行到第 𝑛 + 𝑧 + 1 行,每行 𝑚 个整数以空格隔开,数字代表区域的状况,0 表示马路,1表示建筑。 输出格式: 输出区域新的状态,共 𝑛 行,每行 𝑚 个整数,以空格隔开,代表马路和建筑的数字 不变,使用 2 表示被灯照亮的地方,路灯所在坐标也视为被照亮
时间: 2023-05-21 19:05:52 浏览: 531
city_position.rar_city_城市 坐标_城市链表
这是一道经典的图形处理题,需要使用搜索和遍历算法。以下是实现的大致思路:
1. 读取输入数据,将区域矩阵和灯的坐标分别存储在二维数组里
2. 对于每一个路灯,从其坐标处开始搜索,向上下左右四个方向遍历,将灯能够照亮的区域标记为2
3. 最后输出更新后的区域矩阵
以下是实现的 Python 代码示例:
```
m, n, z = map(int, input().split())
area = []
for i in range(n):
if i == 0:
continue
elif i <= z:
x, y = map(int, input().split())
area.append((x, y))
else:
row = list(map(int, input().split()))
area.append(row)
for x, y in area:
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
while 0 <= nx < n and 0 <= ny < m and area[nx][ny] != 1:
area[nx][ny] = 2
nx += dx
ny += dy
for row in area:
print(' '.join(map(str, row)))
```
对于输入数据:
```
5 5 2
1 1
3 2
1 1 1 1 0
0 0 0 1 0
0 1 0 1 1
0 0 0 0 1
1 1 1 0 0
```
输出如下:
```
2 2 2 2 0
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 1 2 2
```
阅读全文