经典问题的另类解法——以信息学奥赛一本通c++版1216红与黑为例

题目链接：信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

题目描述：

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入：

包括多组数据。每组数据的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:

1）‘.’：黑色的瓷砖；

2）‘#’：白色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每组数据中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

这道题在一本通的分类为搜索与回溯算法，但在这里，我们要引出另一种方法——黏菌法。

想必大部分人是对这个路线规划大师黏菌有所耳闻的，黏菌的基本机理就是走所有的路，然后去掉没用的，到无路需走时结束，而我们的想法就是让初始瓷砖“@”作为黏菌的母菌，不断探索，如果一个黑瓷砖四周有“@”则会被扩散成“@”，不断扩散，因为每次可扩散时至少扩散一个且能扩散到所有能到达的地方，故使用while循环，令每次循环增加“@”数为delta，当delta=0时扩散结束，统计“@”数量即可。

代码如下↓

#include
using namespace std;
int m,n,delta=-1,s=0,t=0,f=0;//delta=-1保证while的进行
int a[25][25];
char q;
int main()
{
	while(cin>>m>>n&&m!=0&&n!=0)
	{
	
		s=0;
		t=0;
		delta=-1;
	for(int i=1;i<=24;i++)
	for(int j=1;j<=24;j++)
	a[i][j]=0;//硬核初始化数组。	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin>>q;
		if(q=='.') a[i][j]=1;
		if(q=='#') a[i][j]=2;
		if(q=='@') a[i][j]=3;
	}//转换格式，方便后续
	while(delta!=0)
	{
	t=s;
	s=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	  {
	  if(a[i][j]==1&&((a[i-1][j]==3)||(a[i][j-1]==3)||(a[i][j+1]==3)||(a[i+1][j]==3))) a[i][j]=3;//扩散的判断（注意是判断这个格子会不会被扩散）
		if(a[i][j]==3) s++;
		}	
	  	delta=s-t;
	}
	s=0;//重新统计数量
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	if(a[i][j]==3) s++;
	cout< 
同样的，比如1215迷宫也可判断出口会不会被入口扩散到，1219马走日可将扩散规则加以改变，8皇后则可以将皇后设为母菌并改变扩散规则，可以认为几乎所有搜索题都能转为图形并运用
 
————作者吐槽时间————
 
纯粹是深搜学不会了。