求助P2895
  • 板块灌水区
  • 楼主Ethan_tang
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/10 13:19
  • 上次更新2024/12/10 19:54:21
查看原帖
求助P2895
1491661
Ethan_tang楼主2024/12/10 13:19

RE3个点,只求条,原题

#include <bits/stdc++.h>
using namespace std;
int m,now,nx[4] = {1,-1,0,0},ny[4] = {0,0,1,-1};
bool at[4000][4000],ma[4000][4000],f,vis[4000][4000];
struct lx
{
	int x;
	int y;
	int t;
};
lx pos(int x,int y,int t)
{
	lx w;
	w.x = x;
	w.y = y;
	w.t = t;
	return w;
}
lx k[50010];
bool cmp(lx x1,lx x2)
{
	return x1.t < x2.t;
}
queue <int> x,y,t;
int main()
{
	cin >> m;
	for (int i = 0;i < m;i++)
	{
		int x3,y3,t3;
		cin >> x3 >> y3 >> t3;
		k[i] = pos(x3,y3,t3);
		at[x3][y3] = 1;
		at[x3 + 1][y3] = 1;
		at[x3 - 1][y3] = 1;
		at[x3][y3 - 1] = 1;
		at[x3][y3 + 1] = 1;
	}
	sort(k,k + m,cmp);
	x.push(0);
	y.push(0);
	t.push(0);
	while (!x.empty())
	{
		int nowx = x.front(),nowy = y.front(),nowt = t.front();
		x.pop();
		y.pop();
		t.pop();
		if (!at[nowx][nowy])
		{
			cout << nowt;
			f = 1;
		}
		while (nowt == k[now].t)
		{
			int x1 = k[now].x,y1 = k[now].y;
			ma[x1][y1] = 1;
			ma[x1 + 1][y1] = 1;
			ma[x1 - 1][y1] = 1;
			ma[x1][y1 - 1] = 1;
			ma[x1][y1 + 1] = 1;
			now ++;
		}
		if (ma[nowx][nowy])
		{
			continue ;	
		}
		for (int i = 0;i < 4;i++)
		{
			int x2 = nowx + nx[i],y2 = nowy + ny[i];
			if (x2 < 0 || y2 < 0) continue ;
			if (!ma[x2][y2] && !vis[x2][y2])
			{
				x.push(x2);
				y.push(y2);
				vis[x2][y2] = 1;
				t.push(nowt + 1);	
			}	
		}
	}
	if(!f) cout << -1;
	return 0;
}
2024/12/10 13:19
加载中...