n138. p10. 病毒傳播 - 高中生程式解題系統

內容

　　在病毒橫行的今天，科學家想要模擬病毒隨時間變化的傳播情形，所以建立一個病毒傳播模型。該科學家的模型把世界切割成規則狀的棋盤狀（參考下方範例中的圖示），每一個格子只有兩種狀態，存在病毒或不存在病毒。一個格子在下一個時間點 $t + 1$ 是否會有病毒是取決於該格子的八個鄰居格子在上一時間點 $t$ 有多少格子存在病毒而決定。
　　如果一個格子在時間點 $t$ 有病毒，且鄰居格子中在時間點 $t$ 有 $2$ 個或 $3$ 個格子有病毒時，此為合適病毒生長的環境，該格的病毒在時間點 $t + 1$ 會繼續存活。但如果一個格子在時間點 $t$ 有病毒，但鄰居格子中在時間點 $t$ 只有小於 $2$ 格或大於 $3$ 格有病毒，該格的病毒在時間點 $t + 1$ 時會死亡。如果一個格子在時間點 $t$ 沒有病毒，但這個格子在時間點 $t$ 的八個鄰居中正好有 $3$ 格存在病毒的話，這個格子在時間點 $t + 1$ 會被繁殖出新病毒。
　　雖然科學家依經驗建立了該病毒傳播模型，但手動計算病毒的傳播情形實在太慢，請你試著幫他寫出一個病毒傳播模擬程式。另外，邊界以外的空間都假定是沒有病毒的狀態，病毒也無法存活。

(初始狀態)

(時間點 1)

(時間點 2,此次模擬最終狀態)

輸入說明

　　第一行有兩個數字，數字間以空格隔開，第一個數字是橫軸的格子數 $X$ ，第二個數字是縱軸的格子數 $Y$ ，且 $X \leq 1024, Y \leq 1024$ 。第二行為一個正整數 $T$ ，表示初始狀態以外，模擬要跑多少次，且 $1 \leq T \leq 2000$ 。接下來會有 $Y$ 行，每一行有 $X$ 個 $0$ 或 $1$ 的數字，並以空格格開，為病毒的初始狀態。 $0$ 代表該格子一開始沒有病毒， $1$ 代表該格子一開始有病毒。

輸出說明

　　每筆測試資料的輸出有 $Y$ 行，每一行有 $X$ 個 $0$ 或 $1$ 的數字（不以空格格開），表示模擬完成後棋盤格中病毒的散布狀態。 $0$ 代表該格子最後沒有病毒， $1$ 代表該格子最後有病毒存在。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1M
公開測資點#1 (5%): 2.0s , <1M
公開測資點#2 (5%): 2.0s , <1M
公開測資點#3 (5%): 2.0s , <10M
公開測資點#4 (5%): 2.0s , <10M
公開測資點#5 (5%): 2.0s , <10M
公開測資點#6 (5%): 2.0s , <10M
公開測資點#7 (5%): 2.0s , <10M
公開測資點#8 (5%): 2.0s , <10M
公開測資點#9 (5%): 2.0s , <10M
公開測資點#10 (5%): 2.0s , <10M
公開測資點#11 (5%): 2.0s , <10M
公開測資點#12 (5%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <10M
公開測資點#16 (5%): 2.0s , <10M
公開測資點#17 (5%): 2.0s , <10M
公開測資點#18 (5%): 2.0s , <10M
公開測資點#19 (5%): 2.0s , <10M

提示：

測資問題
本題原測資範圍 $X, Y \leq 1024$ 、 $20 \leq T \leq 2000$ ，似乎沒有既存算法可以解決，本人暫且將測資範圍修改為 $X, Y \leq 1024$ 、 $1 \leq T \leq 100$ ，若您有辦法處理原題測資，歡迎來信或公開討論，本人會再進一步修改測資範圍並重測所有代碼，造成不便深感抱歉。

標籤:

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
41863	lbm00138 (A是蘋果 B是香蕉)	n138		136	2024-09-03 02:12