题解：AT_abc377_c [ABC377C] Avoid Knight Attack

Nottingham_Forest · 2024-10-30 13:17:05 · 题解

题目大意

在一个 N \times N 的棋盘上，有 M 个棋子被放置在指定的位置。你的目标是在不被这些棋子攻击的情况下，找到可以放置自己棋子的空格数量。

假设一个棋子的位置为 (i,j)，则它可以攻击的位置如下：

思路

首先，这道题暴力枚举是过不了的，我们需要 map 和 pair 这两个东西。

介绍：

map

pair

感谢这位博主与这位博主。

那么，我们就可以用 make_pair 把坐标存起来，注意本身有棋子的地方也算，然后用 map 维护即可。

答案就是格子总数 - 有棋子的地方，也就是 n \times n- map 大小。

存坐标的话就可以用两个数组数组把每次 i,j 加的数存起来，再用原来的加即可。

注意不开 long long 见祖宗还有判边界。

CODE

#include<bits/stdc++.h>
#define int long long//开long long
using namespace std;
map<pair<int,int>,int> mp;//要把映射类型改成pair
int n,m,x0,y2,dx[]={2,1,-1,-2,-2,-1,1,2},dy[]={1,2,2,1,-1,-2,-2,-1},nx,ny;//dx和dy是i,j每次加的
bool check(int h,int z)
{
    if(h>=1&&h<=n&&z>=1&&z<=n)  return true;
    return false;
}//判边界
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x0>>y2;
        mp[make_pair(x0,y2)]=1;//本身有棋子的地方也算
        for(int j=0;j<8;j++)
        {
            nx=x0+dx[j],ny=y2+dy[j];//现在的坐标
            if(check(nx,ny))//如果在边界里才算
            {
                mp[make_pair(nx,ny)]=1;//标记
            }
        }
    }
    cout<<n*n-mp.size();//注意是没棋子的地方
    return 0;
}

时间复杂度

时间复杂度约为 O(m \times \log(n^2))，可通过本题。