几个岛

python解法

经典的岛屿问题，又掏出了我的祖传代码。
不过题目有坑：

• 要判断行数与列数有没有越界。
• 还有越界后的处理，发现测试用例中对于越界还是取上一次的结果，这个使用数组记录上一次操作后岛屿的数量即可。
• 一开始要在res数组里做一个初始化值0，防止一上来就越界，此时岛屿数量为0。

代码如下：

import copy


class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid: return 0
        row, col = len(grid), len(grid[0])
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    res += 1
                    self.merge(grid, i, j)

        return res

    def merge(self, grid, i, j):
        row = len(grid)
        col = len(grid[0])

        if i < 0 or i >= row or j < 0 or j >= col or grid[i][j] != "1":  # 退出dfs的条件：1.越界；2.遇到值为0或者已访问的节点(X)
            return

        grid[i][j] = "X"  # 置为"X", 表示该元素已被访问。
        """向四个方向查找"""
        self.merge(grid, i - 1, j)
        self.merge(grid, i + 1, j)
        self.merge(grid, i, j - 1)
        self.merge(grid, i, j + 1)


m, n, k = [int(input()) for _ in range(3)]
land, grid = [["0" for i in range(n)] for j in range(m)], []
solution = Solution()
res = [0]
for i in range(k):
    row, col = map(int, input().split())
    if row < m and col < n:
        land[row][col] = "1"
        grid = copy.deepcopy(land)
        res.append(str(solution.numIslands(grid)))
    else:
        res.append(res[-1])
print(" ".join(res[1:]))

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// function declaration
int Find(int* p, const int x) {
  return p[x] = p[x] ^ x ? Find(p, p[x]) : x;
}

void Union(int* p, const int u, const int v, int* count) {
  const int pu = Find(p, u);
  const int pv = Find(p, v);
  if (pu == pv) return;
  p[pu] = pv;
  --(*count);
}

void printAnswer(int* ans, int ansSize) {
  int i;
  for (i = 0; i < ansSize; ++i) {
    printf("%d", *(ans + i));
    if (i < ansSize - 1) putchar(32);
  }
  putchar('\n');
}

int main(const int argc, const char** argv) {
  int i, m, n, k, x, y, nx, ny;
  scanf("%d%d%d", &m, &n, &k);
  
  int board[m][n], p[m * n], count = 0;
  memset(board, 0x0000, sizeof board);
  for (i = 0; i < m * n; ++i) *(p + i) = i;
  
  static const int dirs[] = { 0, -1, 0, 1, 0 };
  
  int ans[10000], ansSize = 0;
  while (k--) {
    scanf("%d%d", &y, &x);
    if (x < 0 || x >= n || y < 0 || y >= m || board[y][x]) { // 坐标超出地图边界或已经是一块陆地
      *(ans + ansSize++) = count;
      continue;
    }
    board[y][x] = 1; ++count;
    for (i = 0; i < 4; ++i) {
      nx = x + *(dirs + i), ny = y + *(dirs + i + 1);
      if (nx < 0 || ny < 0 || nx == n || ny == n || !board[ny][nx])
        continue;
      Union(p, y * n + x, ny * n + nx, &count);
    }    
    *(ans + ansSize++) = count;
  }
  
  return printAnswer(ans, ansSize), 0;
}

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 200;
int m, n, k; // 行数m，列数n
int p[N * N];
int g[N][N];

int get(int i, int j) {
    return i * n + j;
}


int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> m >> n >> k;
    int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

    // 并查集
    // 1. 初始化并查集
    for (int i = 0; i < m * n; i ++) p[i] = i;

    // 初始化二维地图

    // 2. 对于每个要变成陆地的点1，看它周围相连的有几个大陆，如果有4个不同的大陆，则大陆数减去3，res -= (t - 1)  t表示不同大陆的数量

    // 3. 注意输入的数据可能有重复的，所以重复了你要怎么办
    // 如果这个坐标已经变过陆地了，那直接返回当前的陆地数就行了

    int cnt = 0; // 表示当前的大陆数量

    vector <vector<int> > seg(k, vector<int>(2));
    for (int i = 0; i < k; i ++) {
        cin >> seg[i][0] >> seg[i][1];
    }

    for (int _ = 0; _ < seg.size(); _ ++) {
        int i = seg[_][0], j = seg[_][1];

        // 如果这个坐标已经变过陆地了，或者这个坐标不合法
        // 那直接返回当前的陆地数就行了
        if (g[i][j] == 1 || (i < 0 || i >= m || j < 0 || j >= n)) { 
            cout << cnt << " ";
            continue;
        }

        g[i][j] = 1; // 当前点变为1
        unordered_set <int> st;

        for (int d = 0; d < 4; d ++) {
            int x = i + dx[d], y = j + dy[d];
            if (x >= 0 && x < m && y >= 0 && y < n) {
                if (g[x][y] == 1) {
                    st.insert(find(get(x, y)));
                    p[find(get(i, j))] = find(get(x,y)); // 合并当前相邻的大陆
                }
            }
        }
        cnt -= (st.size() - 1);
        cout << cnt << " ";
    }



    return 0;
}

核心思想只有一句（注释那行）：

新的岛屿数目 = 原有岛屿数目 + 1 - 现添加位置的联通桥数目

这里的联通桥，指该点与原集合中存在相邻上下左右点(岛)的数目

#islandNum = islandNum+1-countBridge !!!
row,col,optNum = int(input()),int(input()),int(input())
land,islandNum,island = [],0,''
for i in range(optNum):
    addLand = list(map(int,input().split()))
    if addLand[0]>row-1 or \
        addLand[1]<col-1:
        pass
    else:
        loc = (addLand[0],addLand[1])
        bridgeNum = 0
        if loc not in land:
            bridgeNum += int((loc[0]-1,loc[1]) in land)+ \
                 int((loc[0]+1,loc[1]) in land)+ \
                 int((loc[0],loc[1]-1) in land)+ \
                 int((loc[0],loc[1]+1) in land)            
            land.append(loc)
            islandNum += 1-bridgeNum
        if islandNum==0: islandNum = 1
    island += str(islandNum)+' '
print(island[:-1])

public class Main/*CountIslands*/ {
  // 4个方向
  final static int[][] dir = {{1, -1, 0, 0}, {0, 0, 1, -1}};
  // 将二维信息行号r、列号c根据总列数cor映射成一维
  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) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int isNum, row, col, i, r, c, opNum, 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' : ' ');
      }
    }
  }
}

#include <bits/stdc++.h>
using namespace std;

int n, m, k, id=1;
int G[101][101]={0}, dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void DFS(int x, int y, int t){
    G[x][y] = t;
    for(int i=0;i<4;i++){
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(xx>=0 && xx<m && yy>=0 && yy<n && G[xx][yy]!=0 && G[xx][yy]!=t)
            DFS(xx, yy, t);
    }
}

int F(int x, int y){
    int d=1, t=0;
    for(int i=0;i<4;i++){
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(xx>=0 && xx<m && yy>=0 && yy<n && G[xx][yy]!=0){
            if(t == 0){     // 连到第一个岛
                t = G[xx][yy];
                d--;
            }else{
                if(G[xx][yy] != t){     // 与第一个岛联通
                    DFS(xx, yy, t);
                    d--;
                }
            }
        }
    }
    if(t == 0)      // 独立的岛
        G[x][y] = id++;
    else
        G[x][y] = t;
    return d;
}

int main(){
    int s = 0, x, y;
    scanf("%d%d%d", &m, &n, &k);
    while(k--){
        scanf("%d%d", &x, &y);
        if(x>=0 && x<m && y>=0 && y<n && G[x][y]==0)
            s += F(x, y);
        printf("%d ", s);
    }
    return 0;
}

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Iterator;
public class Main{
    //定义全局的方向向量,便于用循环来遍历四个方向
     public static int[][] dir=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
   
    public static void main(String[] args){
        /**
        *1.前期准备工作
        */
        Scanner in=new Scanner(System.in);
        //获取统计参数:行数/列数/操作数
        int rows=in.nextInt();
        int columns=in.nextInt();
        int actions=in.nextInt();
          
        //构造一个地图的数据结构,
                //record[][][0]: 0为水 1为陆地
                //record[][][1]: 唯一标志,标识这个陆地属于哪个岛屿,=加入岛屿的土地数量-1;
        int[][][] record=new int[rows+2][columns+2][2];
 
        //超范围的容器是为了不用判断边界,把边界周围的水也表示出来
        boolean[][] visited=new boolean[rows+2][columns+2];
        
        //设置一个单增序号nextNum,每次添加一块陆地的时候,都会使得该序号增大,
        //可以作为地块的计数.
        //定义一个
        int count=0;
        int nextNum=0;
        
         /**
        *2.操作循环
        */
        while(actions>0){
            int row=in.nextInt()+1;
            int col=in.nextInt()+1;
            int waters=0;
            //利用其去重性,来判断一块地将要连接起来的岛屿数量,表示为set.size();
            Set<Integer> set=new HashSet<Integer>();
             
          /**
        *2.1 当该坐标已经访问过,或者该坐标不在地图范围,则输出当前的岛屿数量
        *    同时操作循环数量自减,这俩不可省略
        *    为了满足要求"结尾无空格",输出时需要判断
        */          
            if(row>rows||col>columns||row<0||col<0|| record[row][col][0]==1){
                if(actions>0){
                    System.out.print(count+" ");
                }else{
                    System.out.print(count);
                }
                 actions--;
                continue;
            }
          /**
        *2.2 如果没有超出地图范围,并且当前是新加入的陆地,则对周围环境进行检索
        *2.2.1记录新地块周围的水的边界数量,以及岛屿的数量(即record[][][1]的值的种类,同一岛屿该值相同,该值为岛屿唯一识别代码)
        *2.2.2判断周围水的边界数量,如果4面都是水,则岛屿计数+1,否则进入下一步;
        *2.2.3判断周围的
        */ 
            //如果没有超出范围,则设置当前位置为陆地,并给他唯一识别符号,同时识别符自增;
            record[row][col][0]=1;
            record[row][col][1]=nextNum++;
            for(int i=0;i<4;i++){          
                int temprec=record[row +dir[i][0]][col+dir[i][1]][0];
                if(temprec==0){
                    waters++;//如果相邻是水,记录周围有多少的水
                }else{
                    set.add(record[row +dir[i][0]][col+dir[i][1]][1]); //如果周围是土地,记录是属于多少个岛屿,将其代号加入其中
                }
            }
            if(waters==4){
                count++;//如果是4面都是水,则认为新增一个陆地,否则就是相连的
            }else {
                count=count-set.size()+1;//否则就是加入了别的岛屿,岛屿数量更新(可能会合并)
                /*3.
                *更新连接的岛屿的全部标识代号*/
                new Main().dfs(row,col,record,new boolean[rows+2][columns+2],nextNum-1);//然后把这个岛的全部位置都遍历一遍,写为新的值
            }
            /**
            *输出格式控制*/
             if(actions>0){
                    System.out.print(count+" ");
                }else{
                    System.out.print(count);
                }
            actions--;//更新当前剩余操作步数
        }
         
    }
      
    /*
    *作用:当前土地加入到了原来的岛屿,或者连接了多个岛屿,此函数基于深度优先原理用于
    *更新当前土地连接的岛屿的所有土地的唯一标识为最新加入元素的标识,一家人整整齐齐,
    *便于下次判断*/
    public  void dfs(int rows,int columns,int[][][] record,boolean[][] visited,int num){
        if(visited[rows][columns]||record[rows][columns][0]==0){
            return;//访问过,或者说是水,则跳过
        }
        visited[rows][columns]=true;//开始访问,写一个访问标记
        record[rows][columns][1]=num;
        for(int i=0;i<4;i++ ){
            dfs(rows+dir[i][0],columns+dir[i][1],record,visited,num);//开始向四面八方递归
        }
    }
  
}

# 给定一个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 1 2 3

def run(m,n,coors):
    '''mxn的岛屿，初始化全是水(0)，本函数将给定的k个坐标coors所在位置变成岛屿(1)，并计算每次修改后的岛屿数量'''
    grid=[[0 for _ in range(n)] for _ in range(m)]

    k=len(coors)# coors:kx2

    res=[0]# 存储最终答案

    def dfs(grid,visited,i,j):
        visited[i][j]=1
        
        for delta_i,delta_j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            new_i,new_j=i+delta_i,j+delta_j
            if 0<=new_i<=m-1 and 0<=new_j<=n-1 and not visited[new_i][new_j] and grid[new_i][new_j]==1:
                dfs(grid,visited,new_i,new_j)


    def get_cur_ans(grid,visited):
        m,n=len(grid),len(grid[0])
        ans=0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1 and not visited[i][j]:
                    ans+=1
                    dfs(grid,visited,i,j)
        return ans



    for kk in range(k):
        x,y=coors[kk]

        # 判断输入的坐标是否越界
        if x<0&nbs***bsp;x>m-1&nbs***bsp;y<0&nbs***bsp;y>n-1:
            res.append(res[-1])
            continue

        grid[x][y]=1

        visited=[[0 for _ in range(n)] for _ in range(m)]#0:未访问；1：已访问
        ans=get_cur_ans(grid,visited)

        res.append(ans)
    
    return res[1:]

while True:
    try:
        m=int(input())
        n=int(input())
        k=int(input())
        coors=[]
        for _ in range(k):
            x,y=map(int, input().split(' '))
            coors.append([x,y])
        res=run(m,n,coors)
        res=map(str,res)
        res=' '.join(res)
        print(res)
    except:
        break

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int row = in.nextInt();
            int col = in.nextInt();
            int[][] grid = new int[row][col];
            int num = in.nextInt();
            int count = 0;
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < num; i++){
                int r = in.nextInt();
                int c = in.nextInt();
                if(isValid(row,col,r,c)){
                    count = 0;
                    grid[r][c] = 1;
                    int[][] temp = new int[grid.length][grid[0].length];
                    //深拷贝
                    for (int k = 0; k < grid.length; k++) {
                        temp[k] = Arrays.copyOf(grid[k], grid[k].length);
                    }
                    for(int a = 0; a < temp.length; a++){
                        for(int b = 0; b < temp[0].length; b++){
                            if(temp[a][b] == 1){
                                count++;
                                dfs(temp,a,b);
                            }
                        }
                    }
                }
                sb.append(count);
                sb.append(" ");
            }
            System.out.println(sb.toString().trim());
        }
    }
    //将与grid[a][b]相邻的陆地都标记为海洋
    public static void dfs(int[][] grid, int a, int b){
        if(!isValid(grid.length, grid[0].length, a, b) || grid[a][b] == 0) return;
        else{
            grid[a][b] = 0;
            dfs(grid,a - 1,b);
            dfs(grid,a + 1,b);
            dfs(grid,a,b + 1);
            dfs(grid,a,b - 1);
        }
    }

    //判断输入合法性
    public static boolean isValid(int row, int col, int r, int c){
        if(r < 0 || r >= row || c < 0 || c >= col) return false;
        return true;
    }
}

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

int find(vector<int>& pa, int x)
{
    return x==pa[x]?x:pa[x]=find(pa, pa[x]);
}

int main()
{
    int m, n, k;
    const int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
    while (scanf("%d%d%d", &m, &n, &k) != EOF)
    {
        int total = m*n;
        vector<int> isWater(total, true);
        vector<int> pa(total);
        for (int i = 0; i < total; ++i) pa[i] = i;
        int count = 0, x, y;
        int curp, newp;
        while (k--)
        {
            scanf("%d%d", &y, &x);
            curp = y*n+x;
            if (x<0||x>=n||y<0||y>=m||!isWater[curp])
            {
                printf("%d ", count);
                continue;
            }
            count++;
            isWater[curp] = false;
            for (int d = 0; d < 4; ++d)
            {
                int newx = x+dx[d], newy = y+dy[d];
                newp = newy*n+newx;
                if (newx<0||newx>=n||newy<0||newy>=m||isWater[newp]) continue;  // 超过边界
                // 周围有陆地
                int paCur = find(pa, curp), paNew = find(pa, newp);
                if (paCur != paNew)  // 两块陆地原本不在一个岛屿，需要合并
                {
                    count--;
                    pa[paCur] = paNew;
                }
            }
            printf("%d ", count);
        }
    }

    return 0;
}