题目描述
给定一个m行n列的二维地图, 初始化每个单元都是水.
操作addLand 把单元格(row,col)变成陆地.
岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).
在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.
二维地图的每条边界外侧假定都是水.
输入描述:
多组测试数据，请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。
输出描述:
一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开，结尾无空格
示例1
输入
复制
3
3
4
0 0
0 1
1 2
2 1
输出
复制
1 1 2 3
#include<vector>
#include<iostream>
using namespace std;
int m,n,k;
int main(){
cin >> m >> n >> k;
int Max = 0;
vector<int> Result;
vector<vector<int>> Map(m,vector<int>(n,0));
for(int i = 0;i < k;i ++){
int x,y;int LianTong = 0;
cin >> x >> y;
if(Map[x][y] == 1 || x < 0 || y < 0 || x >=m || y >= n){
Result.push_back(Max);
continue;
}
Map[x][y] = 1;
if(x - 1 >= 0 && Map[x - 1][y] == 1){
LianTong++;
}
if(x + 1 < m && Map[x + 1][y] == 1){
LianTong++;
}
if(y - 1 >= 0 && Map[x][y - 1] == 1){
LianTong++;
}
if(y + 1 < m && Map[x][y + 1] == 1){
LianTong++;
}
Max = max(Max - LianTong + 1,1);
Result.push_back(Max);
}
for(int i = 0;i < Result.size() - 1;i ++){
printf("%d ",Result[i]);
}
printf("%d",Result[Result.size() - 1]);
return 0;
}
结题思路：
Max为前k-1次操作得到的陆地数量
当下标超出范围或者Map[i][j]==1的时候，vector直接压入
当Map[i][j] != 1的时候，判断Map[i][j]的上下左，变量LianTong自加一
Max = max(Max - LianTong + 1,1)，这里为啥需要和1比较呢，假设两个环互不相交，而(i,j)这个点变成陆地后，这两个环相交了，那么我们的Max-LianTong就是负数，而事实上我们得到的是一个联通的陆地，尴尬！
