返回小组 开始 2019-11-03 08:30:00

201910月赛(入门组)

结束 2019-11-07 21:30:00
Contest is over.
当前 2024-11-22 09:09:57

D. 连锁反应

描述

用一个矩阵(m行n列)来模拟一面墙,这面墙贴有瓷砖,若位置(i,j)上有瓷砖,那么该位置的值为数字1,否则为数字0。规定:一片瓷砖如果不是在墙的顶部、或者至少有一片瓷砖和它相连,那么它就会脱落

我们会依次消除一些瓷砖。每当我们消除 (i, j) 位置时, 对应位置的瓷砖(若存在)会消失,然后其他的瓷砖可能因为这个消除而落下。

现要求你编程求出每次消除操作对应落下的瓷砖数目。

输入

第一行,两个整数,m、n,表示墙的大小。(1<=m、n<=200)

接下来的m行,每行n个元素,0 、1分别表示瓷砖状态。

第m+2行,整数k,表示有几个消除瓷砖的位置。

接下来k行,每一行表示一个位置(i,j)。

输出

k个整数,空格隔开,表示对应每次消除操作后对应的落下的瓷砖数目。

样例

输入

2 4
1 0 0 0
1 1 0 0
2
1 1
1 0

输出

0 0

提示

样例说明:当我们消除(1, 0)的瓷砖时,(1, 1)的瓷砖已经由于上一步消除而消失了。所以每次消除操作不会造成瓷砖落下。注意(1, 0)瓷砖不会记作落下的瓷砖。

1、可以保证每次的消除都不相同,并且位于墙的内部。

2、一个消除的位置可能没有瓷砖,如果这样的话,就不会有瓷砖落下。


Submit

登录

注册
时间限制 1 秒
内存限制 256 MB
提交