AT_fuka_liquid.流れ

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有一个w×hw\times h的网格,网格上的每个格子都有对应的高度。

现在,往方格上倒水。

当某个方格内有水,而相邻的方格又比此方格低时,水就会向相邻的方格扩散。

两个方格在有同一条边时被认为是相邻的。

求一格水扩散的方格数量。

输入格式

输入文件有多组数据,输入三个00表示结束。

对于每组数据,用以下形式给出。

w  h  pw\;h\;p

Z0,0  Z0,1⋯ ⁣Z0,w−1Z_{0,0}\;Z_{0,1}\cdots\!Z_{0,w-1}
Z1,0  Z1,1⋯ ⁣Z1,w−1Z_{1,0}\;Z_{1,1}\cdots\!Z_{1,w-1}
⋯\cdots
Zh−1,0,Zh−1,1⋯ ⁣Zh−1,w−1Z_{h-1,0},Z_{h-1,1}\cdots\!Z_{h-1,w-1}

X1Y1X_{1} Y_{1}
⋯\cdots
XpYpX_{p} Y_{p}

其中每组数据的第一行为33个整数w,h,pw,h,p,

其中w,hw,h表示网格的边长,pp表示倒水的次数。

接下来hh行,每行ww个整数Zi,jZ_{i,j},

表示第ii行第jj列的方格的高度。

接下来pp行,每行22个整数Xi,YiX_{i},Y_{i},

表示在第XiX_{i}行第YiY_{i}列的方格倒水。

数据存在往倒过水的方格再次倒水的情况。

测试数据不超过2020个。

输出格式

对于每组测试数据,输出一行一个整数,表示水扩散到的方格数量。

输入样例

2 2 1
1 0
0 1
1 0
2 2 1
1 0
0 1
1 1
1 1 0
100
5 5 2
5 4 5 5 5
5 3 5 1 5
5 2 1 2 5
5 3 5 3 5
5 5 5 5 5
0 0
2 2
0 0 0

输出样例

1
3
0
5

说明/提示

1≤w,h≤201\leq w,h\leq 20
0≤p≤w×h0\leq p\leq w \times h
0≤Zi,j≤1000\leq Z_{i,j}\leq 100
0≤Xi<w0\leq X_{i}<w
0≤Yi<h0\leq Y_{i}<h

输入解题思路,AI测评打分。不知道怎么写?

首页