### 题目描述

N X N的国际象棋棋盘上有K个车,第i个车位于第Ri行，第Ci列。求至少被一个车攻击的格子数量。

## 第一次尝试 暴力枚举

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

char a[10005][10005] = {0};

int main()
{
long long sum = 0;
int n = 0, k = 0, x = 0, y = 0;

cin >> n >> k;

for(int i = 0; i < k; i++)
{
cin >> x >> y;
a[x - 1][y - 1] = '*';//把棋子标记为“*”
}

for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(a[i][j] == '*')
{
for(int q = 0; q < n; q++)
{
if(a[i][q] != '*')
{
a[i][q] = 'y';//棋子可以攻击到的地方就标记为“y”(yes)
}
}
for(int q = 0; q < n; q++)
{
if(a[q][j] != '*')
{
a[q][j] = 'y';
}
}
}
}
}

for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(a[i][j] == 'y' || a[i][j] == '*')
{
sum++;//统计
}
}
}

cout << sum;

return 0;
}
``````

## 第二次尝试

``````#include<iostream>
#include<cstdio>
using namespace std;

bool jx[1000000010] = {0}, jy[1000000010] = {0};

int main()
{
long long n = 0, k = 0, x = 0, y = 0, sum = 0, cnt = 0;

cin >> n >> k;

for(long long i = 0; i < k; i++)
{
scanf("%lld%lld", &x, &y);
jx[x] = 1;
jy[y] = 1;//桶标记
}

for(long long i = 1; i <= n; i++)
{
if(jx[i] != 0)
{
sum = sum + n;
cnt++;//行的攻击范围
}
}

for(long long i = 1; i <= n; i++)
{
if(jy[i] != 0)
{
sum = sum + n - cnt;//列的攻击范围，为了不与行重复所以使用cnt
}
}

cout << sum;

return 0;
}
``````

## 第三次尝试

（深蓝为重复攻击处）

``````#include<iostream>
#include<cstdio>
using namespace std;

long long jx[1000005] = {0}, jy[1000005] = {0};

bool find(long long a[], long long i, long long x);

int main()
{
long long n = 0, k = 0, sum = 0, xcnt = 0, ycnt = 0, x = 0, y = 0;

cin >> n >> k;

for(long long i = 0; i < k; i++)
{
scanf("%lld%lld", &x, &y);
if(i == 0)
{
jx[i] = x;
jy[i] = y;
}
else//寻找前面有没有和当前的重复的，没有再放进数组（其实就是去重）
{
if(find(jx, i, x))
jx[i] = x;
if(find(jy, i, y))
jy[i] = y;
}
}

for(int i = 0; i < k; i++)
{
if(jx[i] != 0)
{
xcnt++;//统计行
}
if(jy[i] != 0)
{
ycnt++;//统计列
}
}

sum = xcnt * n + ycnt * n - xcnt * ycnt;//用公式计算

cout << sum;

return 0;
}

bool find(long long a[], long long i, long long x)
{
bool rt = false;
int j = 0;
while(j < i)
{
if(x == a[j])
{
break;
}
j++;
}
if(j == i)
{
rt = true;
}

return rt;
}
``````