前言

一切都发生在另一个神秘的中午。 Mod 发了一道题，题目是这样的：

题目描述

小 Z 是一位聪明的僵尸，他打算进攻N*M个方格组成的矩形草坪，但是可恶的戴夫种植了一堆土豆地雷，如果小 Z 踩到了土豆地雷(' * ')，那么他就会爆炸。

但是小Z是一只聪明的僵尸，他不像他的兄弟们，他可是会拐弯的僵尸，但是他不能出草坪，也不能斜着走。

现在他想问问你，他该怎么走，才能走到门口('#')，如果能，输出最小步数，否则输出 "I can't eat brain!"。

输入格式

第一行输入由空格隔开的两个整数：n,m 表示行数和列数

接下来N行，每行输入m个字符，表示草坪，没有土豆地雷的地方为 '.' , 初始点为 'z'

输出格式

如果可以走到门口，输出最少步数（不算起点）

否则输出 'I can't eat brain!'(不带引号)

样例

3 3
.#.
***
..z

I can't eat brain!

数据范围

保证$1≤n,m≤30$

问题

这是一道很正常的搜索对吧。但是我闲着没事干，就想给他多加几个样例。 想给他加一个 $100\times100$ 和一个 $300\times300$ 的样例。于是问题就出现在这里。这是我生成输入数据的代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
	srand(time(0)); // 简单的随机数生成 
	freopen("t10.in", "w", stdout); // 题号 
	
	const int N = 100, M = 100; // 范围 
	cout << N << " " << M << "\n"; // N * M 
	
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			if (i == 1 && j == 1)
			{ // 第一格是门 
				cout << "#";
			}
			else if (i == N && j == M)
			{ // 最后一格是僵尸 
				cout << "z";
			}
			else
			{ // 随机生成 . 和 *  
				int a = rand() % 10;
				if (a <= 1)cout << "*";
				else cout << ".";
			}
		}
		cout << "\n";
	}
	return 0;
}

看起来好像没什么问题吧？

这是我的答案：

#include <iostream>
#include <queue>
using namespace std;
int m, n, a[305][305], sx, sy, ex, ey;
int dx[] = {0, 0, 0, 1, -1}, dy[] = {0, 1, -1, 0, 0};
struct stu{int x, y, step;};

bool check(int x, int y)
{
	if (x < 1 or x > n or y < 1 or y > m)return 0;
	if (a[x][y] == 1)return 0;
	return 1;
}

int bfs()
{
	queue <stu> q;
	q.push(stu{sx, sy, 0});
	while (q.size() != 0)
	{
		stu f = q.front();
		q.pop();
		if (f.x == ex && f.y == ey)
		{
			return f.step;
		}
		for (int i = 1; i <= 4; i++)
		{
			int nx = f.x + dx[i];
			int ny = f.y + dy[i];
			if (check(nx, ny))
			{
				a[nx][ny] = 1;
				q.push(stu{nx, ny, f.step + 1});
			}
		}
	}
	return -1;
}

int main()
{
	freopen("t10.in", "r", stdin);
	 
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			if (c == 'z')
			{
				sx = i;
				sy = j;
				a[i][j] = 1;
			}
			if (c == '*')
			{
				a[i][j] = 1;
			}
			if (c == '#')
			{
				ex = i;
				ey = j;
			}
		}
	}
	int ans = bfs();
	if (ans == -1)cout << "I can't eat brain!";
	else cout << ans;
	return 0;
}

好像也没什么问题吧？而且用 Mod 自己造的 $30\times30$ 以内的数据是对的。

但是问题就是出现了。每次 我用输入数据程序生成 $100\times100$ 的数据时，无论 怎样调整生成土豆地雷的概率，输出 都 是 $\color{red}198$ 。但是我调整门或小 z 的位置，就能得到不一样的答案。

一下是一些数据：

• 范围： $100\times114$ ，答案： $212$ ；
• 范围： $300\times300$ ，答案： $598$ ；
• 通项公式： $n+m-2$ 。
• 从 $40$ 左右就开始乱输出， 大概 $30$ 以内是正确的。
• 答案 总是 # 和 z 的曼哈顿距离。

难道是我的答案有问题？还是 BFS 的局限性？

已经问过 DeepSeek ，但是回答含糊不清。它说是 BFS 入队时标记错误，结果在给我的代码中自己又在入队时标记。