3915 - 电路布局

题目描述

某电子工厂正在设计一块大型电路板,该板子可以看作一个由单位方格组成的平面网格。

工厂将按顺序在网格上逐步放置 N 个电子元件,第 i 个元件放置在坐标为 (x_i, y_i) 的方格中。

在电路板上,一个已放置的电子元件被称为是“被激活的”,当且仅当它在水平和竖直四个方向上(即上、下、左、右)恰好有 3 个相邻的已放置元件(相邻指两个方格共享一条边)。

随着元件的逐个放置,原本处于激活状态的元件可能会因为邻居数量变为 4 而失去激活状态,而原本未激活的元件也可能因为邻居数量增加到 3 而进入激活状态。

请你编写程序,在每放置一个元件后,实时统计并输出当前电路板上所有处于“被激活”状态的元件数量。

输入

第一行一个整数 N,表示元件的总数。

接下来 N 行,每行两个整数 x_iy_i,表示第 i 个元件放置的位置。

输出

N 行,第 i 行表示前 i 个元件全部放置完成后,处于“被激活”状态的元件数量。

样例

输入

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

输出

0
0
0
1
0
0
1
2

输入

10
5 5
5 4
5 6
4 5
6 5
4 4
4 6
6 4
6 6
7 5

输出

0
0
0
1
0
0
1
2
4
3

输入

18
10 10
10 11
11 10
10 9
9 10
11 11
9 11
10 12
11 9
9 9
11 12
9 12
10 8
12 10
8 10
12 11
11 8
12 9

输出

0
0
0
1
0
0
1
0
1
3
4
6
5
4
3
2
3
3
说明

样例说明 1

  • 放置前 3 个元件后,没有任何元件拥有 3 个邻居。
  • 放置第 4 个元件后,位于 (1,1) 的元件恰好与 (0,1), (1,0), (1,2) 三个元件相邻,被激活,输出 1
  • 放置第 5 个元件 (2,1) 后,(1,1) 的邻居数变为 4,失去激活状态,输出 0
  • 放置全部 8 个元件后,位于 (2,1)(2,2) 的元件均恰好有 3 个邻居,处于激活状态,输出 2

数据范围

对于 100\% 的数据,满足 1 \leq N \leq 10^50 \leq x_i, y_i \leq 1000,所有元件的位置互不相同。

测试点编号N
1 \sim 31 \le N \le 400
4 \sim 101 \le N \le 10^5
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 入门


上一题 下一题