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