学步园

1、从该连通块上的任意一点画一射线，射线当然要画在边界上，因为这样处理会很方便 ；（从第一个'X'往下连线）
2、状态：(i, j, s)表示到达点(i, j)时，是否穿过射线的状态为s的最小步数 ；
3、要加以限制，使得只能从一个方向穿过射线 ；（限制从左到右）

4、从起点开始bfs所有状态，最后ans = min{f[i][j][0] + f[i][j][1]}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}
struct data{
	int x,y;
	bool e;
}q[5001];
int n,m,lx=-1,ly,sx,sy,best[51][51][2];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1} ;
bool mp[51][51];
bool pd(int x,int y){
	if(x>=1&&y>=1&&x<=n&&y<=m&&mp[x][y]==1)return 1;
	else return 0;
}
void bfs(){
	int head=0,tail=0;
	memset(best,-1,sizeof(best));
	q[0]=(data){sx,sy,0};
	best[sx][sy][0]=0;
	while(head<=tail){
		data t=q[head++];
		for(int i=0;i<8;i++){
			int a=t.x+dx[i],b=t.y+dy[i];
			if(pd(a,b)){
				bool e=t.e;
				if((t.x<=lx&&a<=lx)||(t.x>lx&&a>lx)||(t.y>=ly&&b>=ly)){
					if(best[a][b][e]==-1){
						best[a][b][e]=best[t.x][t.y][e]+1;
						q[++tail]=(data){a,b,e};
					}
				}
				else if(t.x<=lx){
					if(best[a][b][1]==-1){
						best[a][b][1]=best[t.x][t.y][e]+1;
						q[++tail]=(data){a,b,1};
					}
				}
			}
		}
	}
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		char ch[51];
		scanf("%s",ch+1);
		for(int j=1;j<=m;j++){
			if(ch[j]=='.')mp[i][j]=1;
			else if(ch[j]=='*')sx=i,sy=j;
			else if(lx==-1)lx=i,ly=j;
		}
	}
	bfs();
	int ans=0x7fffffff;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(best[i][j][0]!=-1&&best[i][j][1]!=-1&&best[i][j][0]+best[i][j][1]<ans)
				ans=best[i][j][0]+best[i][j][1];
	printf("%d",ans);
	return 0;
}