spfa挂在了#7
查看原帖
spfa挂在了#7
133116
Xhesika_Frost楼主2020/9/20 19:00
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#define int long long
using namespace std;
int ma[600][600];
int n,m;
int x;
int p;
int u,v;
pair <int,int> q[2500101],xxx;
queue <pair <int,int > > qu;
int mx[4]={0,0,1,-1};
int my[4]={1,-1,0,0};
int dis[600][600];
int vis[600][600];
int ans;
signed main(){
	int maxx;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
		scanf("%d",&ma[i][j]);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			if(x==1){
				p++;
				q[p].first=i;
				q[p].second=j;
			} 
		}
	}
	if(p==0){
		cout<<0;
		return 0;
	}
	qu.push((pair<int,int>){q[1].first,q[1].second});
	memset(dis,0x3f,sizeof(dis));
	maxx=dis[1][1];
	vis[q[1].first][q[1].second]=1;
	dis[q[1].first][q[1].second]=0;
	while(!qu.empty()){
		xxx=qu.front();
		qu.pop();
		u=xxx.first;
		v=xxx.second;
		vis[u][v]=0;
		for(int i=0;i<=3;++i){
			int uu=u+mx[i];
			int vv=v+my[i];
			if(uu<1||vv<1||uu>n||vv>m)
			continue;
			if(abs(ma[u][v]-ma[uu][vv])<dis[uu][vv]){
				if(ma[u][v]==ma[uu][vv]&&dis[uu][vv]!=maxx)
				continue;
				dis[uu][vv]=(abs(ma[u][v]-ma[uu][vv]));
				if(!vis[uu][vv]){
					vis[uu][vv]=1;
					qu.push((pair<int,int>){uu,vv});
				}
			}
		}
	}
	for(int i=2;i<=p;++i){
		ans=max(ans,dis[q[i].first][q[i].second]);
	}
	cout<<ans;
	return 0;
}
2020/9/20 19:00
加载中...