41. 岛屿数量

// 本题使用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; // 答案
    int num = 1; // 编号
    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++;
        // 将新岛屿编号,num是不断增加的,故不会重复
        grid[x][y] = num;
        unordered_set<int> st; // 用来储存不同的岛屿
        // 将新的编号存入set
        st.insert(grid[x][y]);
        // 遍历四个方向
        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;
        // 将所有与当前操作的岛屿连通的岛屿都编号为新的编号num
        dfs(grid, visited, x, y, num);
        // 输出答案
        cout << ans << " ";
        // 预先增加编号
        num++;
    }
    cout << endl;
}
 
int main()
{
    while(cin >> n >> m) {
        solve();
    }
    return 0;
}

//下面是并查集做法
//思路，直接并查集，进行一个连通，那么第一次肯定出现一个岛屿，后面逐渐进行连通
//判断是否当前结点的四周有结点，然后进行连接，如果连接了，就不用++，否则++
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N]; //首先全部都是0，表示全部都是海洋
int m,n;
int find(vector<int>&arr,int x)
{
    if(arr[x]!=x)arr[x]=find(arr,arr[x]);
    return arr[x];
}

void decide(vector<int>&arr,unordered_map<int,int>&map,int &ans)
{
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(g[i][j]==1&&map[find(arr,j*n+i)]!=1)
            {
                ans++;
                map[find(arr,j*n+i)]=1;
            }
        }
    }
}
int main()
{
    cin>>m>>n;
    vector<int> arr(m*n+10);
    for(int i=1;i<arr.size();i++)arr[i]=i;
    int k;cin>>k;
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    while(k--)
    {
        unordered_map<int,int> map;
        int ans=0;
        int x,y;cin>>x>>y;
        if(x<0||x>=n||y>=m||y<0) //防止给出的数据是异常的
        {
            decide(arr,map,ans);
            if(k==0)
                cout<<ans<<endl;
            else 
                cout<<ans<<' ';
            continue;
        }
        g[x][y]=1;
        for(int z=0;z<4;z++)
        {
            int i=dx[z]+x,j=dy[z]+y;
            if(i<0||j<0||i>=n||j>=m||g[i][j]==0)
                continue;
            arr[find(arr,y*n+x)]=find(arr,j*n+i);
        }
        decide(arr,map,ans);
        if(k==0)
            cout<<ans<<endl;
        else 
            cout<<ans<<' ';
    }
    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)