题目链接
// 本题使用dfs
// 总体思路如下:
// 每次进行一个操作, 进行判断
// 如果该操作越界或要操作的地方已经是岛屿了
// 那么跳过此操作, ans不变并且输出ans
// 如果这个操作没问题, 我们将该岛屿编号为ans
// 就检查该操作的上下左右是否有岛屿
// 根据岛屿编号的不同, 我们每发现一个新的编号
// 就说明该编号的岛屿和新添加的岛屿连通了
// 那么岛屿数量 - 1
// 检查完上下左右以后, 我们得到新的ans
// 然后利用dfs把与当前我们操作的岛屿连通的所有岛屿都编号为ans
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; // 表示方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int num) {
// 遍历四个方向
for(int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 跳过越界的情况和海洋
if(nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || visited[nx][ny] == true || grid[nx][ny] == 0) {
continue;
}
// 标记为已经访问过
visited[nx][ny] = true;
// 将该岛屿编号
grid[nx][ny] = num;
dfs(grid, visited, nx, ny, num);
}
}
void solve() {
vector<vector<int>> grid(n, vector<int>(m, 0)); // 地图
int control; // 操作数
cin >> control;
int ans = 0;
while(control--) {
int x;
int y;
cin >> x >> y;
// 如果该操作越界或要操作的地方已经是岛屿就直接输出答案
if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 0) {
cout << ans << " ";
continue;
}
// 岛屿数量增加
ans++;
// 将新岛屿编号
grid[x][y] = ans;
unordered_set<int> st; // 用来储存不同的岛屿
// 遍历四个方向
for(int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 跳过越界的情况和海洋
if(nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 0) {
continue;
}
// 如果出现新的岛屿
// 说明这个岛屿与我们要操作的地方构成连通
// 岛屿数量 - 1 并且将新岛屿加入set
if(!st.count(grid[nx][ny])) {
st.insert(grid[nx][ny]);
ans--;
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false)); // 储存访问情况
// 标记为已经访问
visited[x][y] = true;
// 将编号改为我们新得到的ans
grid[x][y] = ans;
// 将所有与当前操作的岛屿连通的岛屿都编号为我们新得到的ans
dfs(grid, visited, x, y, ans);
// 输出答案
cout << ans << " ";
}
cout << endl;
}
int main()
{
while(cin >> n >> m) {
solve();
}
return 0;
}/**
* 思路：可以使用并查集来解决该问题。每次 addLand 时，可以将新加入的陆地与其相邻的陆地进行合并，
* 然后计算岛屿的数量。
*
* 首先创建一维数组，表示每个单元格的父节点，初始每个单元格的父节点都设置为自己。
* 再初始化一个变量用于记录岛屿的数量
*
* 对于每次 addLand 操作，首先将父节点设置为自己，然后检查周围的上下左右四个单元格，
* 如果相邻的单元格也是陆地，则将当前的单元格与相邻的单元格进行合并（将当前单元格的父节点设置为另外一个单元格）
* 同时岛屿的数量 -1
*
* 每次 addLand 操作后，将当前的岛屿数量存入结果列表。
*/
import java.util.*;
public class Main {
// 4个方向
final static int[][] dir = {{1, -1, 0, 0}, {0, 0, 1, -1}};
/**
* 在并查集中，我们需要为每个单元格或节点分配一个唯一的标识符，以便能够在操作中识别它们。
* 二维地图中的每个单元格可以由其行号和列号唯一确定。然而，并查集的数据结构是基于数组实现的，而数组是一维的。
* 因此，我们需要将二维的坐标映射到一维的索引，以便在数组中表示这些单元格。
* 考虑一个 m 行 n 列的二维地图，可以用 (row, col) 表示其中一个单元格的坐标。
* 通过映射这个坐标到一维数组中的索引，我们可以使用一个一维数组来表示这个二维地图，并进行并查集的操作。
* 映射的方式很多，只需要保证每个单元格都有一个唯一的一维索引，而且不会与其他单元格冲突。
**/
static int hashCor(int r, int c, int col) {
return r * col + c + 1;// 加一是因为要将 0 当作水，加上 1 避免和 0 冲突
}
// 如果par[x] 为 0，则代表该点是水
static int[] par, rank;
static int find(int x) {
return x == par[x] ? x : (par[x] = find(par[x]));
}
static void union(int x, int y) {
if ((x = find(x)) == (y = find(y)))
return;
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}
}
static boolean same(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int isNum; // 当前存在的岛屿个数。
int row, col; // 地图的行数与列数
int i;
int r, c; // 当前正在处理的单元格的坐标
int opNum; // addLand 的总次数
int nearR, nearC; // 相邻单元格的坐标
while (sc.hasNext()) {
row = sc.nextInt();
col = sc.nextInt();
opNum = sc.nextInt();
isNum = 0;
par = new int[row * col + 1]; // 一开始每个点的父节点均为0，代表水
rank = new int[row * col + 1];
while (opNum-- > 0) {
r = sc.nextInt();
c = sc.nextInt();
// 如果行号r和列号c不越界且该点当前是水
if (r >= 0 && r < row && c >= 0 && c < col && find(hashCor(r,c,col)) == 0){
isNum++;
par[hashCor(r, c, col)] = hashCor(r, c, col);
for (i = 0; i < 4; ++i) {//遍历临近 4 个点的坐标
nearR = r + dir[0][i];
nearC = c + dir[1][i];
// 如果该点不越界且是一块陆地且和当前的这一点不属于同一个岛
if (nearR >= 0 && nearR < row && nearC >= 0 && nearC < col &&
find(hashCor(nearR, nearC, col)) != 0 &&
!same(hashCor(nearR, nearC, col), hashCor(r, c, col))) {
// 那么把它们连成同一个岛
union(hashCor(nearR, nearC, col), hashCor(r, c, col));
isNum--;// 因为把两块不同的岛连成同一个岛了，所以岛的数目减一
}
}
}
System.out.printf("%d%c", isNum, opNum==0 ? '\n' : ' ');
}
}
}
}class Island:
def __init__(self, m, n):
self.island = [[(-1, -1) for _ in range(n)] for _ in range(m)]
self.m = m
self.n = n
self.size = {}
self.count = 0 # 初始时有 0 个岛屿
def find(self, x, y):
if self.island[x][y] == (x, y) or self.island[x][y] == (-1, -1):
return self.island[x][y]
x_p, y_p = self.island[x][y]
self.island[x][y] = self.find(x_p, y_p) # 路径压缩
return self.island[x][y]
def union(self, i1, i2):
x1, y1 = i1
x2, y2 = i2
root1x, root1y = self.find(x1, y1)
root2x, root2y = self.find(x2, y2)
if (root1x, root1y) != (root2x, root2y):
if self.size[(root1x, root1y)] < self.size[(root2x, root2y)]:
root1x, root1y, root2x, root2y = root2x, root2y, root1x, root1y
self.island[root2x][root2y] = (root1x, root1y)
self.size[(root1x, root1y)] += self.size[(root2x, root2y)]
self.count -= 1 # 合并后集合数量减少
def add_element(self, x, y):
if self.find(x, y) == (-1, -1):
self.count += 1
self.size[x, y] = 1
self.island[x][y] = (x, y)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if 0 <= new_x < self.m and 0 <= new_y < self.n:
if self.find(new_x, new_y) != (-1, -1):
self.union(i1=(x, y), i2=(new_x, new_y))
def get_count(self):
return self.count
m = int(input())
n = int(input())
island = Island(m=m, n=n)
k = int(input())
res = []
for i in range(k):
x, y = map(int, input().split(" "))
if 0 <= x < m and 0 <= y < n:
island.add_element(x=x, y=y)
res.append(island.get_count())
res = ' '.join(map(str, res))
print(res)