题解：环绕树林的最短路径问题

题目分析

本题要求在网格中找到从起点*出发，环绕由X组成的连续树林一圈并返回起点的最短路径长度。贝西可以水平、垂直或对角线移动，每步算一个单位。关键在于确定环绕树林的“外围路径”，避免穿过树林内部，同时利用广度优先搜索（BFS）计算最短路径。

解题思路

1. 问题建模

   • 树林由连续的X组成，且无空洞，可视为一个实心区域。
   • 起点*位于树林外部，需找到环绕树林的闭合路径。最短路径需紧贴树林边缘，绕过其外围。

2. 关键观察

   • 树林的边界可通过其周围的可通行区域（.或*）确定。
   • 起点需先移动到树林边缘的某点，再沿边缘绕行一周返回起点。由于路径闭合，可将问题拆解为从起点到边缘两点的往返路径之和的最小值。

3. 算法选择

   • 使用BFS计算起点到树林边缘各点的最短距离。由于对角线移动允许，需考虑8个方向的邻域。
   • 找到树林边缘的两个关键位置（如左右边界），分别计算起点到这两个点的往返距离，取最小值作为答案。

代码解释

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 55
#define inf 0x3f3f3f3f
using namespace std;
const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
struct Lux
{
	int x,y;
	Lux(int a,int b):x(a),y(b){}
	Lux(){}
};
char mp[N][N];
int map[N][N];/*0可行，1森林，2枚举线段，3起点*/
int n,m,ans=inf;
int dist[N][N],tx,ty;
 
int in[N][N],cnt;
queue<Lux>q;
int bfs(int sx,int sy)
{
	int i,fr,ret;
	int vx,vy;
 
	for(ret=fr=0;fr<2;fr++)
	{
		memset(dist,0x3f,sizeof(dist));
		while(!q.empty())q.pop();
		for(i=fr*5;i<fr*5+3;i++)
		{
			vx=sx+dx[i];
			vy=sy+dy[i];
			if(in[vx][vy]&&!map[vx][vy])dist[vx][vy]=1,q.push(Lux(vx,vy));
		}
		while(!q.empty())
		{
			Lux U=q.front();q.pop();
			for(i=0;i<8;i++)
			{
				vx=U.x+dx[i];
				vy=U.y+dy[i];
				if(in[vx][vy]&&!map[vx][vy]&&dist[vx][vy]>dist[U.x][U.y]+1)
				{
					dist[vx][vy]=dist[U.x][U.y]+1;
					q.push(Lux(vx,vy));
				}
			}
		}
		ret+=dist[tx][ty];
	}
	return ret;
}
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%s",mp[i]+1);
	for(j=1;j<=m;j++)for(i=1;i<=n;i++)
	{
		in[i][j]=++cnt;
		if(mp[i][j]=='X')
		{
			map[i][j]=1;
			x=i;y=j;
		}
		else if(mp[i][j]=='*')tx=i,ty=j;
	}
	if(tx==x&&ty>y)
	{
		for(i=y;mp[x][i]=='X';i--);
		y=i;
		for(i=y;i;i--)map[x][i]=3;
		for(i=y;i;i--)ans=max(ans,bfs(x,i));
	}
	else
	{
		for(i=y+1;i<=m;i++)map[x][i]=3;
		for(i=y+1;i<=m;i++)ans=min(ans,bfs(x,i));
	}
	printf("%d\n",ans);
	return 0;
}

关键细节

1. 坐标有效性标记
   使用in[i][j]数组标记坐标是否在网格范围内，避免BFS中越界访问。

2. 双向BFS
   在bfs函数中，分两次使用不同的初始方向集（前3个和后3个方向），覆盖环绕树林的两个可能方向，确保计算往返路径的总和。

3. 边缘枚举
   根据起点与树林的相对位置（如右侧或左侧），枚举树林边缘的可通行点，通过标记线段避免重复计算，提高效率。

4. 距离累加
   两次BFS的结果累加，对应从起点到边缘点再返回的总步数，取所有枚举点中的最优解作为答案。

复杂度分析

• 时间复杂度：O(RC8)，每个坐标最多被BFS访问一次，每次扩展8个方向，适用于题目给定的网格规模（R,C≤50）。
• 空间复杂度：O(R*C)，存储距离数组和队列空间。

此解法通过合理的方向枚举和BFS遍历，高效地找到环绕树林的最短路径，确保在给定约束下正确求解。