請佩戴好口罩

題目描述

疫情當下，希望同學們都認真佩戴口罩，保護自己，保護他人。
現假設有一個n*n的網格，每個人分別站在網格中的一個方格上，人們可以選擇佩戴/不佩戴口罩，口罩對于病毒的傳播有如下影響，分為兩種情況：
1. 某人已被感染，若未佩戴口罩，則病毒的“傳染區域”是患者周圍的四個方格；若正確佩戴口罩，則病毒無法傳染其他人。
2. 某人健康，若未佩戴口罩，則只要他位于任意一個患者的“傳染區域”內，就會被傳染；若正確佩戴口罩，則只有他同時位于4個患者的“傳染區域”內時，才會被傳染。
我們將給出網格中每個人的口罩佩戴情況，以及網格中第一個患者的位置，請你計算d天后共有多少患者。

關于輸入

第一行輸入正整數n，表示網格的邊長，1<=n<=100。
接下來輸入網格，n行，每行n個整數，0表示未佩戴口罩，1表示佩戴口罩。
接下來一行是兩個整數，表示第一個感染者在網格中的行、列坐標（規定網格左上角格子的坐標為(0, 0)，右上角格子的坐標為(0, n-1)，以此類推）。
接下來一行是一個正整數，表示天數d，1<=d<=100。

關于輸出

輸出為一行整數，表示經過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天后患者的人數，并輸出。

代碼實現

count=1
n=int(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,y1=map(int,input().split())
days=int(input())
d=1
count=1
q=[]
l=0
class sick:def __init__(self,x1,y1,d):self.x=x1self.y=y1self.day=d
q.append(sick(x1,y1,1))
if mask[x1][y1]==1:print(1)exit()
mask[x1][y1]=2
def pop():global ll+=1
def front():global lreturn q[l]
def push(x):q.append(x)
while l<len(q) and d<=days:p=front()while p.day==d:for i in range(4):nx=p.x+dx[i]ny=p.y+dy[i]if nx>=0 and nx<n and ny>=0 and ny<n and mask[nx][ny]==0:count+=1if d!=days:mask[nx][ny]=2else:mask[nx][ny]=3push(sick(nx,ny,d+1))pop()if l>=len(q):breakp=front()d+=1
for i in range(n):for j in range(n):if mask[i][j]==1:tmp=0for k in range(4):nx=i+dx[k]ny=j+dy[k]if nx>=0 and nx<n and ny>=0 and ny<n and mask[nx][ny]==2:tmp+=1if tmp==4:count+=1
print(count)