3140 - 避开湖泊

题目描述

农夫约翰的农场在最近的暴风雨中被淹没了,更糟糕的是,他的奶牛们死死地怕水。然而,他的保险公司只会根据他农场上最大的“湖泊”的大小来赔偿他。

这个农场被表示为一个矩形网格,有 N(1 \leq N \leq 100) 行和 M(1 \leq M \leq 100) 列。

网格中的每个单元格都是干燥的或者被淹没的,而且恰好有 K(1 \leq K \leq N*M) 个单元格被淹没了。

正如人们所期望的那样,湖泊有一个中心单元格,其他单元格通过共享一个长边(而不是一个角)与该单元格相连。

任何与中心单元格共享一个长边或与任何连接单元格共享一个长边的单元格都成为连接单元格,并且是湖泊的一部分。

输入

1 行:三个用空格分隔的整数:NMK

2K+1 行:

i+1 行描述一个被淹没的位置,由两个用空格分隔的整数 RC 表示其行和列。

输出

最大湖泊包含的单元格数。

样例

输入

3 4 5
3 2
2 2
3 1
2 3
1 1

输出

4
说明

【输入样例说明】

农场是一个有三行四列的网格;五个单元格被淹没了。

它们位于以下位置:(行3,列2);(行2,列2);(行3,列1);(行2,列3);(行1,列1):

# . . .
. # # .
# # . .
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 61
通过人数 21
金币数量 2 枚
难度 基础


上一题 下一题