← 返回题目列表

AtCoder · fuka_liquid

C. 流量

中文机器翻译题面 查看原题

说明 有一个网格

w*h。

网格上的每个方块都有设定的高度。

现在将液体倒在一些方块上。

当某个方格上方存在液体且相邻方格的高度低于该方格的高度时,液体会扩散到相邻方格。然而,当网格上的两个正方形共享一条边时,它们被认为是相邻的。

找出液体扩散的方格数。

输入

输入由多个测试用例组成。 输入的结尾由仅包含三个零的行指示。 每个测试用例均按以下格式给出。

w h p
z_{00} z_{01} … z_{0(w-1)}
z_{10} z_{11} … z_{1(w-1)}
…
z_{(h-1)0} z_{(h-1)1} … z_{(h-1)(w-1)}
x_1 y_1
…
x_p y_p
  • 1 ≦ w,h ≦ 20
  • 0 ≦ p ≦ wh
  • 0 ≦ z_{ij} ≦ 100
  • 0 ≦ x_i < w
  • 0 ≦ y_i < h

测试用例的第一行包含三个整数 写入w,h,p。 w,h分别表示网格的宽度和高度,p代表液体被倒入的次数。

继续h每行包含 w 个整数。z_{ij}。 z_{ij}是 (j,i) 表示正方形的高度。

继续p每行包含两个整数x_i,y_i。 x_i,y_i是 (x_i,y_i) 表示将液体倒入方块中。

但是,液体可以再次倒入已经充满液体的正方形中。

每个文件的测试用例数量保证不超过20个。

输出

对于每个测试用例,打印一行中液体扩散的单元格数量。

示例输入

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