本地IDE没有问题,交上去全TLE,求调
查看原帖
本地IDE没有问题,交上去全TLE,求调
761339
Leonardo_Yang楼主2024/10/3 15:37
#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];
void update(int x,int y,int s){
	vis[x][y]=true,d[x][y]=min(d[x][y],s);
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(0<=nx&&nx<=n&&0<=ny&&ny<=m&&!vis[nx][ny]) update(nx,ny,s+1);
	}
	vis[x][y]=false;
}
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();
		if(x==e.x&&y==e.y) return true;
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(0<=nx&&nx<=x&&0<=ny&&ny<=m&&!vis[nx][ny]&&d[nx][ny]>=mid) 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,0);
			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 15:37
加载中...