7pts求调过样例最后一个bfs标记不加1
查看原帖
7pts求调过样例最后一个bfs标记不加1
1276811
Rain3721楼主2025/6/19 17:13
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int m,x,y,t0,ans;
int a[400][400],b[400][400];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
bool check(int x,int y,int t){
	if(a[x][y]>t) return true;
	return false;
}
struct location{
	int x,y;
}l,t;
queue<location> q;
void bfs(){
	l.x=0;
  	l.y=0;
 	q.push(l);
 	while(!q.empty()){
  		l=q.front();
  		q.pop();
  		for(int i=1;i<=4;i++){
  			t.x=l.x+dx[i];
  			t.y=l.y+dy[i];
  			if(t.x<0||t.y<0) continue;
  			if(check(t.x,t.y,b[l.x][l.y]+1)==false) continue;
  			if(b[t.x][t.y]==-1){
  				b[t.x][t.y]=b[l.x][l.y]+1;
  				if(a[t.x][t.y]==-1){
  					ans=b[t.x][t.y];
  					return;
  				}
  				q.push(t);
			}
  		} 
	}
}
int main(){
  	ios::sync_with_stdio(false);
  	cin>>m;
  	for(int i=0;i<400;i++){
  		for(int j=0;j<400;j++){
  			a[i][j]=-1;
  			b[i][j]=-1;
		}
	}
	b[0][0]=0;
  	for(int i=0;i<m;i++){
 	 	cin>>x>>y>>t0;
  		for(int j=0;j<5;j++){
  			if(a[x+dx[j]][y+dy[j]]==-1||a[x+dx[j]][y+dy[j]]>t0){
  				a[x+dx[j]][y+dy[j]]=t0;
			}
		}
 	}
 	ans=-1;
  	bfs(); 
  	cout<<ans;
	return 0;
}
2025/6/19 17:13
加载中...