穆春旭 @ 2020-03-21 23:21:25
编译通过,样例通过,提交21。对1,3,4;R2;剩下WA.
#include<bits/stdc++.h>
using namespace std;
queue<int>x,y,t;
int m,tt[310][310],maxx,maxy;
bool mp[310][310],vis[310][310];
int xx[5]={0,1,-1,0,0};
int yy[5]={0,0,0,1,-1};
int main()
{
cin>>m;
for(int i=1;i<=m;i++)
{
int x,y,t2;cin>>x>>y>>t2;
maxx=max(maxx,x);
maxy=max(maxy,y);
mp[x][y]=mp[x+1][y]=mp[x][y+1]=true;
if(tt[x][y]==0)tt[x][y]=t2;
if(tt[x+1][y]==0)tt[x+1][y]=t2;
if(tt[x][y+1]==0)tt[x][y+1]=t2;
if(x!=0)
{
if(tt[x-1][y]==0)tt[x-1][y]=t2;
mp[x-1][y]=true;
}
if(y!=0)
{
if(tt[x][y-1]==0)tt[x][y-1]=t2;
mp[x][y-1]=true;
}
}
x.push(0);
y.push(0);
t.push(0);
while(1)
{
int nx=x.front(),ny=y.front(),nt=t.front();
if(mp[nx][ny]==false)
{
cout<<nt;
return 0;
}
for(int i=1;i<=4;i++)
{
int fx=nx+xx[i];
int fy=ny+yy[i];
int ft=nt+1;
if(fx>=0&&fx<=maxx+10&&fy>=0&&fy<=maxy+10&&vis[fx][fy]==0)
{
if(tt[fx][fy]==0||tt[fx][fy]>ft)
{
x.push(fx);
y.push(fy);
t.push(ft);
vis[fx][fy]=1;
}
}
}
x.pop();
y.pop();
t.pop();
}
return 0;
}