几个岛

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);//开始向四面八方递归
        }
    }
  
}

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;
    }
}

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' : ' ');
      }
    }
  }
}