[数据结构与算法]D. Nearest Excluded Points

题目链接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <map>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
#define int long long
typedef pair<int,int>PII;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

signed main()
{
	int n;cin>>n;
	vector<int>x(n),y(n);
	set<PII>S;
	map<PII,int>id;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
		id[{x[i],y[i]}]=i;
	}
	for(int i=0;i<n;i++)
	{
		S.insert({x[i]-1,y[i]});
		S.insert({x[i]+1,y[i]});
		S.insert({x[i],y[i]+1});
		S.insert({x[i],y[i]-1});
	}
	
	vector<PII>res(n,{-1,-1});
	queue<array<int,4>>q;
	for(auto [x,y] : S)
		if(!id.count({x,y}))
			q.push({x,y,x,y});

	while(q.size())
	{
		auto [x,y,fx,fy] = q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
		    int nx=x+dx[i],ny=y+dy[i];
			if(!id.count({nx,ny}))continue;
			res[id[{nx,ny}]]={fx,fy};
			q.push({nx,ny,fx,fy});
			id.erase({nx,ny});
		}
	}
	
	for(auto [x,y] : res)cout<<x<<" "<<y<<'\n';
}