← 返回 uber 的题目列表Number of Islands II
类型：online_judge
Problem: Number of Islands II
Given an m x n grid initially filled with water, perform a sequence of operations positions[i] = [r, c], where each operation turns cell (r, c) into land.
After each operation, return the current number of islands. An island is formed by lands connected horizontally or vertically.
If an operation adds land to a cell that is already land, the grid does not change, but you still need to report the current island count.
Input Format
First line: two integers m n.
Second line: integer k, the number of operations.
Next k lines: two integers r c.
Output Format
Print k integers separated by spaces, the island count after each operation.
Constraints
1 <= m, n <= 10^4
1 <= k <= 10^5
0 <= r < m
0 <= c < n
Example
Input:
3 3
4
0 0
0 1
1 2
2 1
Output:
1 1 2 3
Example
Input
3 3
4
0 0
0 1
1 2
2 1
Output
1 1 2 3