题解：AT_abc203_e [ABC203E] White Pawn

由于

m \le 2 \times 10^{5}

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

CPP

#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;
}

题解：AT_abc203_e [ABC203E] White Pawn

文章操作

相关推荐

评论

题解：AT_abc203_e [ABC203E] White Pawn