58分蒟蒻 求救
查看原帖
58分蒟蒻 求救
469821
喝脉动割动脉楼主2022/10/10 17:28

58分蒟蒻 求救

#include<bits/stdc++.h>
#define re register

using namespace std;
struct vec{
	int x,y,num;
};
int xx,yy,zz,nx,ny,nnum,a[310][310],jx[4]={-1,0,0,1},jy[4]={0,-1,1,0};
bool vis[310][310];

inline int bfs(int x,int y,int step){
	queue<vec> q;
	q.push(vec{x,y,step});
	vis[x][y]=1;
	while(!q.empty()){
		xx=q.front().x,yy=q.front().y,zz=q.front().num;
		q.pop();
		for(int i=0;i<4;++i){
			nx=xx+jx[i],ny=yy+jy[i],nnum=zz+1;
			if(nx>=0&&ny>=0){
				if(a[nx][ny]==0x3f3f3f3f){
					return nnum;
				}
				if(!vis[nx][ny]&&nnum<a[nx][ny]){
					q.push(vec{nx,ny,nnum});
					vis[nx][ny]=1;
				}
			}
		}
	}
	return -1;
}

int main(){
	int n,x,y,ti;
	scanf("%d",&n);
    memset(a,0x3f,sizeof(a));
	for(re int i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&ti);
		a[x][y]=min(a[x][y],ti);
		for(int j=0;j<4;++j){
			if(x+jx[j]>=0&&y+jx[j]>=0)
				a[x+jx[j]][y+jy[j]]=min(a[x+jx[j]][y+jy[j]],ti);
		}
	}
	printf("%d",bfs(0,0,0));
	return 0;
}
2022/10/10 17:28
加载中...