Tokitsukaze 家里有 $k$ 只猫。现实中 $k$ 为 5(与本题无关),如下图所示:

众所周知 Tokitsukaze 特别懒,在家从不搞卫生,搞卫生这事都是由 Tokitsukaze 的老婆 TomiokapEace 一手包办。在 TomiokapEace 搞卫生时,它们总是会上窜下跳,特别碍事,于是她想做一些措施让它们无法移动。

现在把 Tokitsukaze 的家看作是一个 $n×m$ 的网格,第$i$ 只猫的位置在 $(x_i, y_i)$。TomiokapEace 想用若干片防猫网来限制猫的移动,她将在一只猫所在格子的四周各放上一片防猫网。

一片防猫板是位于两个相邻格子间隔,长度为1个单位的障碍物,可以阻止猫移动。具体来讲,当猫位于 $(x, y)$ 时,若 $(x-1, y), (x, y-1), (x+1, y), (x, y+1)$ 中的任意一格和 $(x, y)$ 之间不存在防猫板,则猫可以向相邻格子移动。

TomiokapEace 想知道至少需要购买多少片防猫网才能使所有猫无法移动。

输入格式

第一行包含三个整数 $n, m, k (1≤n, m≤300; 1≤k≤n⋅m)$,表示 Tokitsukaze 家的大小为 $n×m$,以及家里有 $k$ 只猫。

接下来 $k$ 行,每行两个整数 $x_i, y_i (1≤x_i ≤n; 1≤y_i ≤m)$,表示第 $i$ 只猫的位置。保证所有猫的位置互不相同。

输出格式

输出一个整数,表示 TomiokapEace 至少需要购买防猫网的数量。

输入样例:

5 4 3
3 2
4 3
4 4

输出样例:

11

输入样例:

1 1 1
1 1

输出样例:

4

题目分析

一只猫贡献 4 个围栏, 读入猫时判断其周围是否已经有猫即可(某方向有猫则在某方向减少一个围栏)。

代码实现

#include <iostream>
#include <unordered_map>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
using LL = long long;
const int N = 310, M = N * N;

int n, m, k, ans;
PII dir[4] = {{-1,0},{1,0},{0,-1},{0,1}};
unordered_map <int, unordered_map <int,bool>> cat;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < k; ++i) {
        int x, y, cnt = 4;
        cin >> x >> y;
        cat[x][y] = 1;
        for(int k = 0; k < 4; ++k) {
            int I = x + dir[k].x, J = y + dir[k].y;
            if(I >= 1 && I <= n && J >= 1 && J <= m) cnt -= cat[I][J];
        }
        ans += cnt;
    }
    cout << ans;
    return 0;
}
分类: Thought

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status