HNUSTOJ-1521 塔防游戏

1521: 塔防游戏

时间限制: 1 Sec 内存限制: 128 MB
提交: 117 解决: 38
[提交][状态][讨论版]

题目描述

小明最近迷上了塔防游戏，塔防游戏的规则就是在地图上建炮塔，用于防御敌军的进攻。

这里我们假设地图是一个n行m列的格子，每个炮塔只能建在格子里，这里的炮塔有点奇怪，因为它只能攻击它自己所在行和所在列的格子（包括自身），并且每两个塔既不能放在同一列也不能放在同一行；现在小明建好了cnt个塔，小明一看这cnt个塔的攻击范围刚好把地图割成了S个炮塔攻击不到的区域，因为区域太多了，小明没法数，小明想知道答案S是多少，你能帮助他吗？

输入

有多组测试数据；每组测试数据的格式如下：

第一行输入两个数n,m分别表示地图有n行m列个格子(1<=n<=100000,1<=m<=100000)；

接下来一行输入一个数cnt表示小明建好的塔数(1<=cnt<=Min(n,m));

接下来的cnt行，每行输入两个数r,c表示每个塔在地图上的位置（1<=r<=n,1<=c<=m）；

输出

每组测试数据输出一个数S（如上所述），占一行；

样例输入

样例输出

提示

sample的解释：如图所示，地图是一个5行5列的格子，在（2,2），（3,3）处有两个炮塔，阴影部分为这两个炮塔的攻击范围，最后地图被这两个炮塔的攻击范围分成了4个无法攻击到的区域，所以答案是4；

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int N =  + ;

int x[N], y[N];

int main(){

    int n, m, k;

    while(scanf("%d %d", &n, &m) == ){

        scanf("%d", &k);

        for(int i = ; i < k; i++) scanf("%d %d", &x[i], &y[i]);

        int cntx = , cnty = ;

        sort(x, x + k);

        if(x[] != ) cntx++;

        for(int i = ; i < k; i++)

            if(x[i] != x[i-] + ) cntx++;

        if(x[k-] == n) cntx--;

        sort(y, y + k);

        if(y[] != ) cnty++;

        for(int i = ; i < k; i++)

            if(y[i] != y[i-] + ) cnty++;

        if(y[k-] == m) cnty--;

        printf("%d\n",(cntx+) * (cnty+));

    }

}

巴特西

HNUSTOJ-1521 塔防游戏

1521: 塔防游戏

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章