题目传送门

思路

首先，我们可以发现，当前 $(1,1)$ 位置是什么脚印，那最后走的动物就是哪一个。而因为脚印会相互覆盖，且我们要求来的动物的最小值，所以每一种动物是交替来的。

这时候，问题就成了求连通块（由题意得，连通 的定义为四面连通）。每一次将连通块的脚印变成另一种动物的脚印。这样能持续多少次，就有几只动物来过。

这里求连通块可以使用广搜求解。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 4e3 + 5;

struct point
{
	int x, y;
};

int h, w, cnt, ans;
bool flag;
char mp[N][N];
bool vis[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
queue<point> q[2]; // 分别记录两个脚印的队列

void bfs(int t) // 广搜
{
	int x = t & 1; // 哪一种动物（交替）
	q[x].push({1, 1});
	vis[1][1] = 1;
	while (q[x].size())
	{
		point u = q[x].front();
		q[x].pop();
		for (int i = 0; i < 4; i++)
		{
			int bx = u.x + dx[i], by = u.y + dy[i];
			if (bx <= 0 || bx > h || by <= 0 || by > w || mp[bx][by] == '.' || vis[bx][by]) continue;
			vis[bx][by] = 1;
			if (mp[bx][by] == mp[u.x][u.y]) q[x].push({bx, by});
			else // 还有没有其他动物来过
			{
				q[x ^ 1].push({bx, by});
				flag = 1;
			}
		}
	}
}

int main()
{
	scanf("%d%d", &h, &w);
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			cin >> mp[i][j];
	flag = 1;
	while (flag)
	{
		flag = 0, cnt++;
		bfs(cnt);
		ans++;
	}
	printf("%d\n", ans);
	return 0;
}