[CSP-S模拟测试]:新的世界（BFS）

题目背景

　　小学五六年级的乔猫是一个喜欢不务正业写游戏的孩纸$......$他曾经模仿著名的沙盒游戏《$Minecraft$》做过一个自己的游戏$"NEWorld"$。这两个游戏有着相同的规则，都是通过在一个满是方块组成的$3D$世界中，放置不同的方块来建造各种各样的东西。对了，游戏中还有一个独特的“近似全局光照”的亮度系统$......$为了简单，我们只考虑二维的情况吧。

题目描述

　　在一个$N$行$M$列的网格中，第$i$行$j$列的格子有一个可变的“亮度”$L_{ij}$（初始时都为$0$）和一个固定的“不透光度”$A_{ij}$。现在在$r$行$c$列放入一个亮度为$l$的光源，$NEWorld$游戏引擎会根据以下逻辑，让光源逐步“照亮”附近的方格：
　　先将光源所在方格的亮度$L_{rc}$赋值为$l$。而对于$i$行$j$列一个不是光源的方格，它的亮度由$A_{ij}$和四周方格的亮度所确定。定义$F(i,j)=\max\{L_{i−1,j},L_{i+1,j},L_{i,j−1},L_{i,j+1},A_{ij}\}−A_{ij}$（此处当$1\leqslant i'\leqslant N$不成立或$1\leqslant j'\leqslant M$不成立时，$L_{i'j'}$被看作是$0$），我们称方格$(i,j)$的亮度$L_{ij}$是“有效”的，当且仅当$L_{ij}=F(i,j)$。显然初始时所有亮度都是“有效”的，而放入光源后则可能存在亮度“无效”的方格。
　　现在引擎会循环执行操作，每一步找出当前所有亮度“无效”（不包括光源）的方格中，行数$i$最小的那一个（如果有多个行数$i$最小的，就选择其中列数$j$最小的方格），然后计算$F(i,j)$的值，将其赋值给$L_{ij}$。操作会不停地执行，直到所有亮度都“有效”为止（请参考样例，循环一定会在有限步操作后结束）。请问最后$p$行$q$列的方格亮度值$L_{pq}$是多少？
　　注：$\max\{a,b,c,d,e\}$表示取$a,b,c,d,e$中最大的值。

输入格式

　　输入文件名为$neworld.in$。
　　输入文件第一行两个正整数$N,M$，表示网格大小为$N$行$M$列。
　　接下来的$N$行，每行$M$个正整数，其中第$i$行$j$列的正整数为$A_{ij}$。
　　最后一行包含五个正整数$r,c,l,p,q$，表示在$r$行$c$列放入亮度为$l$的光源，需要查询的是亮度计算完成后$p$行$q$列的亮度值。

输出格式

　　输出文件名为$neworld.out$。
　　输出文件包含一行一个正整数，表示最后$L_{pq}$的值。

样例

样例输入：

4 4
1 1 1 1
1 4 4 1
1 1 4 1
1 1 1 1
3 2 4 1 1

样例输出：

数据范围与提示

样例解释：

　　这张图展示了亮度重新计算的过程。数字表示方格亮度$L_{ij}$，白色方格为光源，灰色方格的灰度表示该方格的不透光度$A_{ij}$（浅灰为$1$深灰为$4$），绿色方格是亮度“无效”的方格，其中深绿色是即将被重新计算亮度的方格。

数据范围：

　　对于$60\%$的数据：$N,M\leqslant 100$。
　　对于$100\%$的数据：$N,M\leqslant 500,1\leqslant A_{ij},l\leqslant 10^9,1\leqslant r,p\leqslant N,1\leqslant c,q\leqslant M$。

题解

正解是$Dijkstra$，但是由于出题人并不会卡$BFS$，于是他只卡了$SPFA$……

所以直接$BFS$就好了，表现蛮好的。

时间复杂度：$\Theta($玄学$)$。

期望得分：$60$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int N,M;

int A[600][600],F[600][600];

int r,c,l,p,q;

queue<pair<int,int> > que;

void BFS()

{

	while(que.size())

	{

		pair<int,int> flag=que.front();que.pop();

		int i=flag.first,j=flag.second;

		if(i>1)

		{

			if(F[i][j]>F[i-1][j]+A[i-1][j])

			{

				F[i-1][j]=F[i][j]-A[i-1][j];

				que.push(make_pair(i-1,j));

			}

		}

		if(i<N)

		{

			if(F[i][j]>F[i+1][j]+A[i+1][j])

			{

				F[i+1][j]=F[i][j]-A[i+1][j];

				que.push(make_pair(i+1,j));

			}

		}

		if(j>1)

		{

			if(F[i][j]>F[i][j-1]+A[i][j-1])

			{

				F[i][j-1]=F[i][j]-A[i][j-1];

				que.push(make_pair(i,j-1));

			}

		}

		if(j<M)

		{

			if(F[i][j]>F[i][j+1]+A[i][j+1])

			{

				F[i][j+1]=F[i][j]-A[i][j+1];

				que.push(make_pair(i,j+1));

			}

		}

	}

}

int main()

{

	scanf("%d%d",&N,&M);

	for(int i=1;i<=N;i++)

		for(int j=1;j<=M;j++)

			scanf("%d",&A[i][j]);

	scanf("%d%d%d%d%d",&r,&c,&l,&p,&q);

	F[r][c]=l;

	que.push(make_pair(r,c));

	BFS();

	printf("%d",F[p][q]);

	return 0;

}

rp++

巴特西