A21239. 国际象棋
填空题
困难
知识点
题目描述
国际象棋
题目描述
有一个 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≤109，1≤M≤2×105，1<=ak、bk<=N，所有棋子位置互不相同，输入均为整数。
参考答案
#include <iostream>
#include <set>
#include <vector>
int main() {
using namespace std;
int N, M;
cin >> N >> M;
set<pair<int, int>> bad_cell;
vector<pair<int, int>> knight_move{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
for (int i = 0; i < M; ++i) {
int x, y;
cin >> x >> y;
bad_cell.emplace(x, y);
for (const auto& move : knight_move) {
int dx = move.first;
int dy = move.second;
if (1 <= x + dx && x + dx <= N && 1 <= y + dy && y + dy <= N)
bad_cell.emplace(x + dx, y + dy);
}
}
cout << static_cast<long>(N) * N - bad_cell.size() << endl;
return 0;
}
上一题
下一题