a115. TOI 2026/03 潛力組：細菌繁殖

題目描述

M 列、N 欄的盤面上，起初有 K 種細菌，各占一個不同格子，編號為 1 到 K。有些格子不適合生存。每分鐘，已被細菌占據的格子會同時向上、下、左、右相鄰的空白可生存格擴散；原本的細菌仍保留。

若多種細菌在同一分鐘抵達同一空格，由編號最小者占據。已占據或不適合生存的格子不會改由其他細菌占據。請計算 T 分鐘後各種細菌的格數。

輸入格式

第一行有正整數 M、N、K、T。接著 M 行各有 N 個整數：−1 表示不可生存，0 表示空格，1 到 K 表示細菌編號。

• 1 ≤ K ≤ M×N ≤ 200000
• 1 ≤ T ≤ 2000000000
• 每一種細菌在初始盤面恰出現一次。

輸出格式

輸出一行 K 個整數，依編號 1 到 K 列出 T 分鐘後各種細菌所占格數。

來源

TOI 2026 年 3 月潛力組〈細菌繁殖〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202603/Bacteria.pdf