DTOI 2018 10.26测试 T1 新的世界

T1 新的世界（neworld）

时间限制: 1 Sec 内存限制: 256 MB

题目描述

在一个$N$N行$M$M 列的网格中，第$i$i 行$j$j 列的格子有一个可变的“亮度”
$L_{i,j}$Li,j​（初始时都为0）和一个固定的“不透光度”。现在在$r$r 行$c$c 列放入一个亮度为$l$l的光源，NEWorld游戏引擎会根据以下逻辑，让光源逐步“照亮”附近的方格：

先将光源所在方格的亮度$\ L_{r,c}$ Lr,c​赋值为$l$l 。而对于$i$i行$j$j 列一个不是光源的方格，它的亮度由$\ A_{i,j}$ Ai,j​和四周方格的亮度所确定。
定义$F_{i,j}=max({L_{i-1,j},L_{i+1,j},L_{i,j-1},L_{i+1,j},L_{i,j+1}})−A_{i,j}$Fi,j​=max(Li−1,j​,Li+1,j​,Li,j−1​,Li+1,j​,Li,j+1​)−Ai,j​（此处当$1≤i′≤N$1≤i′≤N
不成立或$1≤j′≤M$1≤j′≤M不成立时，$L_{i′j′}$Li′j′​被看作是0），我们称方格$(i,j)$(i,j) 的亮度$L_{i,j}$Li,j​是“有效”的，当且仅当$L_{i,j}=F_{i,j}$Li,j​=Fi,j​。显然初始时所有亮度都是“有效”的，而放入光源后则可能存在亮度“无效”的方格。

现在引擎会循环执行操作，每一步找出当前所有亮度“无效”（不包括光源）的方格中，行数$i$i最小的那一个（如果有多个行数$i$i
最小的，就选择其中列数$j$j最小的方格），然后计算$F_{i,j}$Fi,j​ 的值，将其赋值给$L_{i,j}$Li,j​
。操作会不停地执行，直到所有亮度都“有效”为止（请参考样例，循环一定会在有限步操作后结束）。请问最后$p$p行$q$q列的方格亮度值$L_{p,q}$Lp,q​ 是多少？

注：$max (a,b,c,d,e)$max(a,b,c,d,e)表示取$a,b,c,d,e$a,b,c,d,e中最大的值。

输入

输入文件第一行两个正整数$N,M$N,M ，表示网格大小为$N$N 行$M$M 列。

接下来的$N$N行，每行$M$M个正整数，其中第$i$i 行$j$j 列的正整数为$A_{i,j}$Ai,j​

最后一行包含五个正整数$r,c,l,p,q$r,c,l,p,q表示在$r$r 行$c$c 列放入亮度为$l$l 的光源，需要查询的是亮度计算完成后$p$p 行$q$q
列的亮度值。

输出

输出文件包含一行一个正整数，表示最后$L_{p,q}$Lp,q​ 的值。

数据范围

对于$60 \%$60%的数据：$N,M≤100$N,M≤100。

对于$100\%$100% 的数据：$N,M≤500,1≤A_{i,j},l≤10^9,1≤r,p≤N,1≤c,q≤M N,M≤500,1≤A_{i,j},l≤10^9,1≤r,p≤N,1≤c,q≤M$N,M≤500,1≤Ai,j​,l≤109,1≤r,p≤N,1≤c,q≤MN,M≤500,1≤Ai,j​,l≤109,1≤r,p≤N,1≤c,q≤M

题解： 考虑一个点可能会被多次更新，显然不可以直接bfs跑一遍，于是看他有点像最长路的性质，将点权当成类似最短路中的$dis$dis，于是直接跑。考场上是$spfa$spfa和$dijkstra$dijkstra都可以过
（ps.本来出题人本不想卡$spfa$spfa的，但我硬是搞出了一种数据卡$spfa$spfa 2333）

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define re register
#define rep(i,a,b) for(re int i=a;i<=b;i++)
#define repd(i,a,b) for(re int i=a;i>=b;i--)
#define For(i,a,b) for(re int i=a;i<b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
const int N=504;
int a[N][N],c[N][N],n,m,R,C;bool vis[N][N];
typedef pair<int,int>P;
typedef pair<int,P>PP;
priority_queue<PP>q;
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
in void bfs(){
	priority_queue<PP>q;
	q.push(mk(0,mk(R,C)));
	while(!q.empty()){
		PP now=q.top();q.pop();
		P tt=now.se;
		int x=tt.fi,y=tt.se;
		if(vis[x][y]) continue;
		vis[x][y]=1;
		For(i,0,4){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>n||tx<1||ty>m||ty<1) continue;
			if(c[tx][ty]<c[x][y]-a[tx][ty]){
				c[tx][ty]=c[x][y]-a[tx][ty];
				q.push(mk(c[tx][ty],mk(tx,ty)));
			}
		}
	}
}
int main(){
	freopen("neworld.in","r",stdin),freopen("neworld.out","w",stdout);
	g(n),g(m);
	rep(i,1,n) rep(j,1,m) g(a[i][j]);
	g(R),g(C);g(c[R][C]);
	bfs();
	int ax,ay;g(ax),g(ay);
	/*rep(i,1,n){
		rep(j,1,m) cout<<c[i][j]<<" ";
		cout<<endl;
	}*/
	printf("%d\n",c[ax][ay]);
	return 0;
}