41. 岛屿数量(第四期模拟笔试)

内存限制:256 MB 时间限制:1.000 S

题目描述

给定一个 m 行 n 列的二维地图,初始化每个单元格都是海洋,二维地图外也全是海洋。 

操作 addLand 会将单元格(col, row)变为陆地。定义一系列相连的被海洋包围的陆地为岛屿,横向相邻或者纵向相连的岛屿才算相连(斜着相邻的不算)。 

现有一系列的 addLand 操作,给出每次 addLand 操作后岛屿的个数。

输入

第一行为正整数 m 

第二行为正整数 n 

第三行表示 addLand 的操作次数 k 

后续有 k 行输入,每行分别为两个整数,代表 addLand 操作的坐标

输出

输出为一行,k个整数,代表每次 addLand 后地图中岛屿的个数,整数之间用一个空格隔开,最后一个整数后没有空格

样例输入 复制

3
3
4
0 0
0 1
1 2
2 1

样例输出 复制

1 1 2 3

提示

数据范围:

0 < m <= 100;
0 < n <= 100;
0 < k < 1000; 

addLand 的坐标会有非法情况。