网站建设重点步骤,大连如是科技,wordpress原创主题,经典网站代码请佩戴好口罩
题目描述
疫情当下#xff0c;希望同学们都认真佩戴口罩#xff0c;保护自己#xff0c;保护他人。 现假设有一个n*n的网格#xff0c;每个人分别站在网格中的一个方格上#xff0c;人们可以选择佩戴/不佩戴口罩#xff0c;口罩对于病毒的传播有如下影响希望同学们都认真佩戴口罩保护自己保护他人。 现假设有一个n*n的网格每个人分别站在网格中的一个方格上人们可以选择佩戴/不佩戴口罩口罩对于病毒的传播有如下影响分为两种情况 1. 某人已被感染若未佩戴口罩则病毒的“传染区域”是患者周围的四个方格若正确佩戴口罩则病毒无法传染其他人。 2. 某人健康若未佩戴口罩则只要他位于任意一个患者的“传染区域”内就会被传染若正确佩戴口罩则只有他同时位于4个患者的“传染区域”内时才会被传染。 我们将给出网格中每个人的口罩佩戴情况以及网格中第一个患者的位置请你计算d天后共有多少患者。
关于输入
第一行输入正整数n表示网格的边长1n100。 接下来输入网格n行每行n个整数0表示未佩戴口罩1表示佩戴口罩。 接下来一行是两个整数表示第一个感染者在网格中的行、列坐标规定网格左上角格子的坐标为(0, 0)右上角格子的坐标为(0, n-1)以此类推。 接下来一行是一个正整数表示天数d1d100。
关于输出
输出为一行整数表示经过d天后患者的人数。
例子输入
4
0 0 0 1
0 1 0 0
1 0 0 1
0 0 1 0
1 2
5
例子输出
11
解题分析
在python中直接用多层for循环是很慢的Python是一种解释型语言,相对于编译语言,解释器需要更多的时间来解析和执行代码。此外,对于每一次循环迭代,Python需要进行更多的工作,例如变量查找、内存分配等。所以本题如果直接定义一些数组存储信息并用for循环去做的话也不是不可以只是在对于数据量比较大的情况下会导致时间上开销极大。
下面介绍一种利用队列数据结构来优化的方法。我们可以引入队列(queue)数据结构这个结构的特点是头出尾进也就是它只能从尾巴进入队列从队头离开队列。这是可以用数组去模拟的。只要我们在全局过程中维护好我们的一些下标变量和整个的数组结构即可。
我们还需要一个病人类记录发病的人的位置和发病的天数以便我们去判断。
首先通过输入获取了网格的边长n以及网格中每个人的口罩佩戴情况以及第一个患者的位置和天数d。然后使用了队列的数据结构将第一个患者的位置和天数加入到队列中并标记其口罩佩戴情况。接着通过一个while循环不断遍历队列中的元素每次遍历时都会将患者的传染区域内的健康人标记为2同时将传染区域的健康人加入到队列中并标记其天数。在遍历的过程中通过不断pop()和push()操作实现了对队列中元素的处理。最后通过对网格中每个人的口罩佩戴情况进行遍历计算出经过d天后患者的人数并输出。
代码实现
count1
nint(input())
mask[[0 for _ in range(n)] for _ in range(n)]
dx[0,0,-1,1]
dy[-1,1,0,0]
for i in range(n):mask[i]list(map(int,input().split()))
x1,y1map(int,input().split())
daysint(input())
d1
count1
q[]
l0
class sick:def __init__(self,x1,y1,d):self.xx1self.yy1self.dayd
q.append(sick(x1,y1,1))
if mask[x1][y1]1:print(1)exit()
mask[x1][y1]2
def pop():global ll1
def front():global lreturn q[l]
def push(x):q.append(x)
while llen(q) and ddays:pfront()while p.dayd:for i in range(4):nxp.xdx[i]nyp.ydy[i]if nx0 and nxn and ny0 and nyn and mask[nx][ny]0:count1if d!days:mask[nx][ny]2else:mask[nx][ny]3push(sick(nx,ny,d1))pop()if llen(q):breakpfront()d1
for i in range(n):for j in range(n):if mask[i][j]1:tmp0for k in range(4):nxidx[k]nyjdy[k]if nx0 and nxn and ny0 and nyn and mask[nx][ny]2:tmp1if tmp4:count1
print(count)
