塔子哥最近开始研究了植物病毒学,他发现了一种名为 X 的超级病毒,该病毒在农作物间的传染性极强。现有一块 N 行 M 列的农田,每一个格子都栽种着一株植物,每株植物只有感染了病毒和未感染病毒两种状态,假定已经感染病毒的植物用 0 表示,未感染的植物用 1 表示。
塔子哥需要使这块农田里所有植物都感染上病毒,以获得更多的实验材料。已知塔子哥一次操作只能让一株植物感染上病毒,当这一株未感染病毒的植物感染了 X 病毒,那么与它相邻的上、下、左、右、左上、左下、右上、右下这八个方向的未感染植物都会发生感染,进一步地,当一个原本未感染的植物发生感染后,与其相邻的8个方向上的未感染植物均会发生感染。
给定一个样例如下:
1 0 1
0 1 0
1 0 1
按照上述规则,塔子哥最少需要操作 1 次后,所有的植物都会感染X病毒。
请问,给定一个由 0 和 1 组成的农田矩阵,塔子哥最少需要操作几次后,农田里所有植物都会感染上 X 病毒。
第一行输入两个数字 N , M (1≤N,M≤1000),分别表示二维矩阵的行数,列数,并用空格隔开
下面输入 N 行,每行 M 个数字,并用空格隔开
最少需要点击几次后,矩阵中所有数字均为 0 。
输入
3 3
1 0 1
0 1 0
1 0 1
输出
1
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.