图的连通性，注意非法下标的处理情况

题目描述

给定一个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就是负数，而事实上我们得到的是一个联通的陆地，尴尬！