题解：AT_abc203_e [ABC203E] White Pawn

wNv_sakula · 2025-01-05 12:50:39 · 题解

由于 m \le 2 \times 10^{5}，所以可以把有黑格子的行扔到一个 map 里面，然后再用一个 set 存储当前能走到哪些格子。按照题意暴力转移，开两个 vector in 和 out，分别存储哪些格子要删掉，哪些格子要加入。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    map<int,vector<int>> Map;
    set<int> Set;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        Map[x].push_back(y);
    }
    Set.insert(n);
    for(auto i:Map)
    {
        vector<int> in,out;
        for(int j:i.second)
        {
            if(Set.count(j)) out.push_back(j);
            if(Set.count(j-1)||Set.count(j+1)) in.push_back(j);
        }
        for(int j:out) Set.erase(j);
        for(int j:in) Set.insert(j);
    }
    printf("%d",Set.size());
    return 0;
}