日期：2026年8月30日
ZeroJudge 題目連結：s214.細菌繁殖 (Bacteria)
題目 pdf 檔連結：細菌繁殖 (Bacteria)
解題想法
題目為多筆測資。測資開頭為 $M, N, K, T$ 四個整數，分別代表地圖為 $M$ 列、$N$ 欄；共有 $K$ 種細菌，編號為 $1$ ~ $K$；回傳經過時間 $T$ 之後各種類細菌數量。接下來有 $M$ 列、每列 $N$ 個整數，數字 0 代表目前沒有細菌的格子，$-1$ 代表無法走到的格子，正整數代表這格的細菌編號。如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格。測資範圍為 $K \leq M \times N \leq 2 \times 10^5$，$T < 2 \times 10^9$。
這題考 BFS，從一開始有細菌的格子出發，每次檢查上、下、左、右的格子是否為 0，直到沒有格子可以佔領或是時間到為止。為了配合「如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格」的規則，先掃過一開始的地圖 $grid$，將有細菌的格子座標依照細菌編號填入長度為 $K+1$ 的二維陣列 $sources$ 之中；接下來將 $sources$ 的資料，依照細菌編號由小到大放入待走訪佇列 $que$ 之中，這樣在用 BFS 向外傳播時，編號小的細菌會先抵達格子，直接修改 $grid$ 此格的編號，如果之後有編號較大的細菌也走到這格時就無法佔領。
這題還有一些陷阱，例如時間 $T$ 最大約為 $2 \times 10^9$，可能在時間還沒到之前地圖上就沒有格子能走了，如果直接用一個 for 迴圈跑 $T$ 次可能會超時。解決方法是用另一個二維陣列 $time$ 儲存格子第一次有細菌抵達的時間，當 BFS 走到某個格子的時間已經等於 $T$ 就可以中止迴圈，或是 $que$ 已經是空的也可以中止迴圈。
另一個陷阱是 Python 才會遇到的記憶體限制 64 MB，如果用 sys.stdin.read().split() 一次讀取所有測資並分割，會超出記憶體上限，要改用生成器，每次轉換一個數字。而且直接用二維串列儲存 $grid, time$ 資料，運算速度會比較慢而且使用較多的記憶體，改用 array 函式庫的 array 並將二維陣列攤平成一維，才樣才能過關。
Python 程式碼
記憶體爆掉，通過 85% 的測資。
def solve():
import sys
from collections import deque
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
# 讀取測資，地圖 grid，有細菌的格子 source，計數器 cnt
M = int(data[ptr])
N = int(data[ptr + 1])
K = int(data[ptr + 2])
T = int(data[ptr + 3])
ptr += 4
grid = []
for _ in range(M):
row = list(map(int, data[ptr : ptr + N]))
ptr += N
grid.append(row)
sources = [[] for _ in range(K + 1)]
cnt = [0] * (K + 1)
for i in range(M):
for j in range(N):
d = grid[i][j]
if d > 0:
sources[d].append((i, j))
cnt[d] += 1
# 從 sources 取出位置加入待走訪序列 que
que = deque()
for source in sources:
for pos in source:
que.append(pos)
# 執行時間等於 T 或是直到 que 為空
time = [[0] * N for _ in range(M)] # 首次有細菌抵達的時
dr = (0, 1, 0, -1)
dc =(1, 0, -1, 0)
while que and time[que[0][0]][que[0][1]] < T:
r, c = que.popleft()
d = grid[r][c]
t = time[r][c]
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < M and 0 <= nc < N and grid[nr][nc] == 0:
grid[nr][nc] = d
time[nr][nc] = t + 1
cnt[d] += 1
que.append((nr, nc))
res = " ".join(map(str, cnt[1:])) + "\n"
result.append(res)
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
解題時間約為 0.4 s，使用記憶體約為 50.9 MB。
def solve():
import sys
from collections import deque
from array import array
# 改用生成器，避免 sys.stdin.read().split() 一次讀取所有測資使記憶體爆掉
def get_tokens():
for line in sys.stdin:
for token in line.split():
yield(int(token))
tokens = get_tokens()
while True:
try:
# 讀取測資，地圖 grid，有細菌的格子 source，計數器 cnt
M = next(tokens)
N = next(tokens)
K = next(tokens)
T = next(tokens)
except StopIteration:
break
# 地圖攤平成一維陣列，grid[r][c] => grid[r*N + c]
MN = M * N
grid = array('i', [0]) * MN
time = array('i', [0]) * MN
cnt = array('i', [0]) * (K + 1)
sources = [[] for _ in range(K + 1)]
for pos in range(MN):
v = next(tokens)
grid[pos] = v
if v > 0:
sources[v].append(pos)
cnt[v] += 1
# 從 sources 取出位置加入待走訪序列 que
que = deque()
for source in sources:
for pos in source:
que.append(pos)
# 執行時間等於 T 或是直到 que 為空
dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)
while que and time[que[0]] < T:
pos = que.popleft()
r, c = pos // N, pos % N
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < M and 0 <= nc < N:
nxt = nr * N + nc
if grid[nxt] == 0:
grid[nxt] = grid[pos]
time[nxt] = time[pos] + 1
cnt[grid[nxt]] += 1
que.append(nxt)
res = " ".join(map(str, cnt[1:])) + "\n"
sys.stdout.write(res)
if __name__ == "__main__":
solve()
C++ 程式碼
解題時間約為 65 ms，使用記憶體約為 24.5 MB。
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
int main() {
int M, N, K, T;
while(scanf("%d %d %d %d", &M, &N, &K, &T) != EOF) {
// 讀取測資，地圖 grid，有細菌的格子 source，計數器 cnt
vector<vector<int>> grid (M, vector<int> (N, 0));
vector<vector<pair<int, int>>> sources (K + 1); // 1 ~ K 種細菌的起始位置
vector<int> cnt (K + 1, 0);
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
int d; scanf("%d", &d);
grid[i][j] = d;
if (d > 0) {
sources[d].push_back({i, j});
cnt[d]++;
}
}
}
// 從 sources 取出位置加入待走訪序列 que
queue<pair<int, int>> que;
for(auto source : sources) {
for(auto pos : source) {
que.push(pos);
}
}
// 執行時間等於 T 或是直到 que 為空
vector<vector<int>> time (M, vector<int> (N, 0)); // 首次有細菌抵達的時
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(!que.empty() && time[que.front().first][que.front().second] < T) {
int r = que.front().first, c = que.front().second;
int d = grid[r][c], t = time[r][c];
que.pop();
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] == 0) {
grid[nr][nc] = d;
time[nr][nc] = t + 1;
cnt[d]++;
que.push({nr, nc});
}
}
}
// 輸出答案
for(int i = 1; i <= K; i++) {
printf("%d", cnt[i]);
if (i == K) printf("\n");
else printf(" ");
}
}
return 0;
}
沒有留言:
張貼留言