第十个点TLE,求调
查看原帖
第十个点TLE,求调
761339
Leonardo_Yang楼主2024/10/3 16:14
#include<bits/stdc++.h>
#define N 510
using namespace std;
struct kxy{
	int x,y,st;
}s,e;
char c[N][N];
int ans=0x7f7f7f7f,n,m,d[N][N],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},l,r,mid;
bool vis[N][N];
inline void update(int x,int y){
	queue<kxy> q;
	q.push({x,y,0}),vis[x][y]=true,d[x][y]=0;
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,st=q.front().st;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i],ns=st+1;
			if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!vis[nx][ny]&&ns<d[nx][ny]) d[nx][ny]=ns,vis[nx][ny]=true,q.push({nx,ny,ns});
		}
	}
}
inline bool ck(int mid){
	queue<kxy> q;
	if(d[s.x][s.y]<mid) return false;
	q.push({s.x,s.y,0}),memset(vis,0,sizeof vis),vis[s.x][s.y]=true;
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,st=q.front().st;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!vis[nx][ny]&&d[nx][ny]>=mid){
				if(e.x==nx&&e.y==ny) return true;
				vis[nx][ny]=true,q.push({nx,ny,st+1});
			}
		}
	}
	return false;
}
int main(){
	cin>>n>>m,memset(d,0x7f,sizeof d);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='+') memset(vis,0,sizeof vis),update(i,j);
			else if(c[i][j]=='V') e={i,j,0};
			else if(c[i][j]=='J') s={i,j,0};
		}
	}
	r=max(d[s.x][s.y],d[e.x][e.y]);
	while(l<r){
		mid=(l+r+1)>>1;
		if(ck(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

2024/10/3 16:14
加载中...