简答题
偏难
#13103
国际象棋 题目描述 有一个 N x N 的巨大棋盘,包含 N^2 个格子。棋盘的行和列都从 1 到 N 编号,格子(i, j) 表示第 i 行第 j 列的格子。…
国际象棋
题目描述
有一个 N x N 的巨大棋盘,包含 N^2 个格子。棋盘的行和列都从 1 到 N 编号,格子(i, j) 表示第 i 行第 j 列的格子。
目前棋盘上已经放置了 M 个马,第 k 只马位于格子 (ak, bk)。每个格子保证最多只能有一个棋子。
请统计,这个棋盘上有多少空格子,不会被任意一只马吃掉。
如果一只马在 (i, j),那么它可以攻击以下 8 个位置(这些位置需要在棋盘边界范围内):
(1)(i + 2, j + 1)
(2)(i + 1, j + 2)
(3)(i - 1, j + 2)
(4)(i - 2, j + 1)
(5)(i - 2, j - 1)
(6)(i - 1, j - 2)
(7)(i + 1, j - 2)
(8)(i + 2, j -1)
输入格式
第一行包含两个整数 N 和 M,分别表示棋盘大小和已有棋子数量。
接下来 M 行,每行包含两个整数 ak 和 bk,表示第 k 个棋子的位置。
输出格式
输出一个整数,表示可以安全放置棋子的空格子数量。
输入样例1
2 1 1 1
输出样例1
3
输入样例2
3 7 3 2 1 3 2 3 3 3 3 1 2 1 1 1
输出样例2
1
数据范围
1≤N≤10^9,1≤M≤2×10^5,1<=ak、bk<=N,所有棋子位置互不相同,输入均为整数。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> horse;
vector<pair<int, int>> pos;
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int main() {
int n, m, coun = 0;
cin >> n >> m;
//由于N的范围较大,不可能使用N*N的数组
//这里计算马能攻击的格子数x, 安全位置则是N*N-x-m
for(int i=0; i<m; i++) {
int x, y, ax, ay;
cin >> x >> y;
horse.push_back(make_pair(x, y));
for(int j=0; j<8; j++) {
ax = x+dx[j];
ay = y+dy[j];
if(ax>=1 && ax<=n && ay>=1 && ay<=n) {
if(find(pos.begin(), pos.end(), make_pair(ax, ay))==pos.end()) {
pos.push_back(make_pair(ax, ay));
}
}
}
}
//统计pos位置包含的马
int k = 0;
vector<pair<int, int>>::iterator it;
for(it=pos.begin();it!=pos.end();it++) {
if(find(horse.begin(), horse.end(), *it) != horse.end())
k++;
}
long long num = (long long)n*n - (m - k);
num -=pos.size();
cout << num;
return 0;
}</pre>
这道题暂未补解析。