为什么TLE#2
查看原帖
为什么TLE#2
1037072
yhl110804楼主2025/1/16 10:04
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=6e2+10;
const int mod=1e9+7;
struct node{
	int x,y,mx;
}kl,tp[300000];
int top;
struct pos{
	int x,y;
};
queue<pos>q;
int dis[N][N];
int n,m;
int a[N][N];
int c[N][N];
int xx[10]={0,0,1,0,-1};
int yy[10]={0,1,0,-1,0};
int ab(int k){
	if(k<0)return -k;
	return k;
}
void dij(int x,int y){
	memset(dis,0x3f3f,sizeof dis);
	dis[x][y]=0;
	q.push((pos){x,y});
	while(!q.empty()){
		pos nw=q.front();
		q.pop();
		for(int i=1;i<=4;++i){
			int x_=nw.x+xx[i];
			int y_=nw.y+yy[i];
			if(x_>n||x_<1||y_>m||y_<1)continue;
			if(dis[x_][y_]>max(dis[nw.x][nw.y],ab(a[nw.x][nw.y]-a[x_][y_]))){
				dis[x_][y_]=max(dis[nw.x][nw.y],ab(a[nw.x][nw.y]-a[x_][y_]));
				q.push((pos){x_,y_});
			}
		}
	}
	int ans=0;
	for(int i=1;i<=top;i++)
	ans=max(ans,dis[tp[i].x][tp[i].y]);
	write(ans);
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;++j){
			c[i][j]=read();
			if(c[i][j]==1) kl.x=i,kl.y=j,kl.mx=0,tp[++top]=kl;
		}
		if(top==0){
			cout<<0<<"\n";
			return 0;
		}
    dij(kl.x,kl.y);
	return 0;
}
2025/1/16 10:04
加载中...