如图所示,在一条宽为 $2$ 、长为 $2×10^9+1$ 的管道中,有一只鸡和若干着火点,鸡可以上下左右移动一格、不能出管道上下边界、不能进入着火地点。

鸡初始在 $(1,0)$ 处,现在给出若干个着火点的坐标,请求出为了不让鸡逃出管道(即到达管道最左端或最右端),最少需要添加多少个着火点。

输入格式

输入第一行包括一个整数 $T(1≤T≤10^4)$ ,用例组数。

每组用例第一行包括一个整数 $n(0≤n≤10^5)$ ,着火点的个数。

随后的第 $i$ 行输入两个整数 $r, c(1≤r≤2,−10^9≤c≤10^9)$ ,表示着火点的坐标 $(r,c)$ ,坐标含义如题图所示。保证着火点不会为 $(1,0)$ 。

保证所有数据的 $n$ 之和 Σ $n≤10^5$ ,保证同一组用例输入中没有重复的着火点坐标。

输出格式

对每组样例,输出一个整数,表示最少需要添加多少个着火点才能使得鸡逃不出管道。

输入样例:

8
1
2 0
4
1 3
2 4
1 -2
2 -2
2
1 4
1 5
2
1 -2
2 4
1
1 -1
5
2 0
1 3
2 2
2 4
2 5
9
1 -5
2 2
2 -3
1 -4
1 -1
1 -3
1 -2
2 -4
2 3
0

输出样例:

2
0
3
2
2
1
1
3

题目分析

观察图可发现, 问题可以分为两个相同的问题——封锁左管道和封锁右管道。 以封锁左管道为例: 只要存在两个火焰,假设其中一个火焰的位置为 fire[x][y] , 那么另一个火焰的位置在:

  • f[x ^ 3][y + 1] (右上或右下)
  • f[x ^ 3][y - 1] (左上或左下)
  • f[x ^ 3][y] (上或下) 那么就能将左管道封锁。

那么我们可以定义一个 cntL 用于表示封锁左管道所需要的火焰数。易知, cntL 的上界为 2(当左管道没有火的时候)。 我们在读入火焰数据时有这些情况: 对于火焰 fire[x][y] 且 y < 0: 那么左管存在火焰,要封锁左管道最多还需要一个火焰, 那么 cntL = 1。

如果:

  • f[x ^ 3][y + 1] (右上或右下)
  • f[x ^ 3][y - 1] (左上或左下)
  • f[x ^ 3][y] (上或下)

那么就能将左管道封锁。 cntL = 0。

右管同理可以计算出 cntR

我们可以发现 fire[2][0], fire[1][-1], fire[1][1] 有一点特殊:

  • fire[2][0] 可以看作是左管的火焰,也可以看作右管的火焰。
  • max{cntL + cntR} = 4, 但是只要 fire[2][0], fire[1][-1], fire[1][1] 都是火焰即可封锁,火焰数为 3。

所以答案应该为: $$ min({3 - fire[1][-1] - fire[1][1] - fire[2][0]}, cntL + cntR); $$

代码实现

#include <iostream>
#include <unordered_map>
using namespace std;

int t;
int solve() {
    int n, cntl = 2, cntr = 2;
    unordered_map <int, unordered_map <int,bool>> fire;
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x, y;
        cin >> x >> y;
        fire[x][y] = 1;
        int X = x ^ 3;
        if(y < 0) {
            cntl = min(cntl, 1);
            if(fire[X][y] || fire[X][y + 1] || fire[X][y - 1]) cntl = 0;
        }
        else if(y > 0) {
            cntr = min(cntr, 1);
            if(fire[X][y] || fire[X][y + 1] || fire[X][y - 1]) cntr = 0;
        }
        else {
            cntl = min(cntl, 1);
            cntr = min(cntr, 1);
            if(fire[1][-1]) cntl = 0;
            if(fire[1][1]) cntr = 0;
        }
    }
    int ans = 3 - fire[1][-1] - fire[1][1] - fire[2][0];
    return min(ans, cntl + cntr);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}
分类: HashThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status