题解 | #几个岛#

解题思路

这是一道动态岛屿统计问题，主要思路如下：

问题分析：
- 给定m×n的二维地图，初始全是水
- 每次addLand操作会将一个格子变成陆地
- 相邻的陆地（上下左右）形成一个岛屿
- 需要统计每次操作后的岛屿数量
解决方案：
- 使用vector存储每个岛屿的点集
- 每次添加新点时检查是否能与现有岛屿相连
- 如果新点能连接多个岛屿，需要合并这些岛屿
- 维护当前岛屿的总数量
实现细节：
- 使用Point结构体表示坐标
- 检查新点与现有岛屿的相邻关系
- 合并相连的岛屿
- 处理边界情况

代码

cpp
java
python

#include <iostream>
#include <vector>
using namespace std;

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

class Solution {
public:
    string countIslands(int r, int c, vector<pair<int,int>>& operations) {
        vector<vector<Point>> points;
        string res;
        int land_number = 0;
        
        for(int i = 0; i < operations.size(); i++) {
            int x = operations[i].first;
            int y = operations[i].second;
            
            if(x >= 0 && x < r && y >= 0 && y < c) {
                bool flag = true;
                int index = -1;
                Point tmp(x, y);
                
                // 检查是否能与现有岛屿相连
                for(int j = 0; j < points.size(); j++) {
                    for(int k = 0; k < points[j].size(); k++) {
                        Point& cur = points[j][k];
                        
                        if(flag) {
                            if((cur.x == x && abs(cur.y - y) <= 1) || 
                               (cur.y == y && abs(cur.x - x) <= 1)) {
                                flag = false;
                                points[j].push_back(tmp);
                                index = j;
                                break;
                            }
                        } else {
                            if((cur.x == x && abs(cur.y - y) <= 1) || 
                               (cur.y == y && abs(cur.x - x) <= 1)) {
                                // 合并岛屿
                                points[index].insert(points[index].end(), 
                                                   points[j].begin(), 
                                                   points[j].end());
                                points.erase(points.begin() + j);
                                land_number--;
                                j--;
                                break;
                            }
                        }
                    }
                }
                
                // 如果是新岛屿
                if(flag) {
                    vector<Point> tmpV;
                    tmpV.push_back(tmp);
                    points.push_back(tmpV);
                    land_number++;
                }
            }
            
            res += to_string(land_number);
            if(i < operations.size() - 1) {
                res += " ";
            }
        }
        return res;
    }
};

int main() {
    int r, c, n;
    cin >> r >> c >> n;
    
    vector<pair<int,int>> operations;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        operations.push_back({x, y});
    }
    
    Solution solution;
    cout << solution.countIslands(r, c, operations) << endl;
    return 0;
}

import java.util.*;

class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static String countIslands(int r, int c, int[][] operations) {
        List<List<Point>> points = new ArrayList<>();
        StringBuilder res = new StringBuilder();
        int landNumber = 0;
        
        for(int i = 0; i < operations.length; i++) {
            int x = operations[i][0];
            int y = operations[i][1];
            
            if(x >= 0 && x < r && y >= 0 && y < c) {
                boolean flag = true;
                int index = -1;
                Point tmp = new Point(x, y);
                
                for(int j = 0; j < points.size(); j++) {
                    List<Point> island = points.get(j);
                    for(Point cur : island) {
                        if(flag) {
                            if((cur.x == x && Math.abs(cur.y - y) <= 1) ||
                               (cur.y == y && Math.abs(cur.x - x) <= 1)) {
                                flag = false;
                                island.add(tmp);
                                index = j;
                                break;
                            }
                        } else {
                            if((cur.x == x && Math.abs(cur.y - y) <= 1) ||
                               (cur.y == y && Math.abs(cur.x - x) <= 1)) {
                                points.get(index).addAll(island);
                                points.remove(j);
                                landNumber--;
                                j--;
                                break;
                            }
                        }
                    }
                }
                
                if(flag) {
                    List<Point> newIsland = new ArrayList<>();
                    newIsland.add(tmp);
                    points.add(newIsland);
                    landNumber++;
                }
            }
            
            res.append(landNumber);
            if(i < operations.length - 1) {
                res.append(" ");
            }
        }
        return res.toString();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int n = sc.nextInt();
        
        int[][] operations = new int[n][2];
        for(int i = 0; i < n; i++) {
            operations[i][0] = sc.nextInt();
            operations[i][1] = sc.nextInt();
        }
        
        System.out.println(countIslands(r, c, operations));
        sc.close();
    }
}

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def count_islands(r: int, c: int, operations: list) -> str:
    points = []  # 存储所有岛屿的点集
    result = []
    land_number = 0
    
    for x, y in operations:
        if 0 <= x < r and 0 <= y < c:
            flag = True
            index = -1
            tmp = Point(x, y)
            
            # 检查是否能与现有岛屿相连
            i = 0
            while i < len(points):
                island = points[i]
                for cur in island:
                    if flag:
                        if ((cur.x == x and abs(cur.y - y) <= 1) or 
                            (cur.y == y and abs(cur.x - x) <= 1)):
                            flag = False
                            island.append(tmp)
                            index = i
                            break
                    else:
                        if ((cur.x == x and abs(cur.y - y) <= 1) or 
                            (cur.y == y and abs(cur.x - x) <= 1)):
                            # 合并岛屿
                            points[index].extend(island)
                            points.pop(i)
                            land_number -= 1
                            i -= 1
                            break
                i += 1
            
            # 如果是新岛屿
            if flag:
                points.append([tmp])
                land_number += 1
        
        result.append(str(land_number))
    
    return ' '.join(result)

def main():
    r = int(input())
    c = int(input())
    n = int(input())
    operations = []
    for _ in range(n):
        x, y = map(int, input().split())
        operations.append((x, y))
    
    print(count_islands(r, c, operations))

if __name__ == "__main__":
    main()

算法及复杂度

算法：并查集的变体
时间复杂度： $\mathcal{O}(k \cdot n)$ - $k$ 为操作次数， $n$ 为岛屿数量
空间复杂度： $\mathcal{O}(k)$ - $k$ 为操作次数