H行W列的迷宫，用2*H+1行的字符串表示，每行最多有2*W+1个字符，省略每行后面的空格。迷宫的边界上有且仅有两个出口，求每个点出发到出口的最短路。

+-+-+-+-+-+|         |+-+ +-+ + +|     | | |+ +-+-+ + +| |     |+-+ +-+-+-+

以每个出口为起点bfs，需要注意的是，最后的距离是（d+1）/2。

/*TASK:maze1URL:http://train.usaco.org/usacoprob2?a=iHr5iXglQfJ&S=maze1LANG:C++*/#include
     
      #include
      
       #include
       
        #include
        
         #define N 305using namespace std;int n,m,dx[5]={
   0,1,0,-1},dy[5]={
   1,0,-1,0},dis[N][N],ans,vis[N][N];char c[N][N];struct node {    int x,y,d;};queue
         
          q;void bfs(){    for(int i=0;i<=2*m;i++)    for(int j=0;j<=2*n;j++)    if(!i||i==2*m||!j||j==2*n)    if(!c[i][j]||c[i][j]==' '){        memset(vis,0,sizeof vis);        q.push((node){i,j,0});        while(!q.empty()){            node t=q.front();            q.pop();            int x=t.x,y=t.y,d=t.d;            if(vis[x][y]||x<0||y<0||x>2*m+1||y>2*n+1||c[x][y]&&c[x][y]!=' ')continue;            vis[x][y]=1;            dis[x][y]=min(dis[x][y],d);            for(int i=0;i<=4;i++)                    q.push((node){x+dx[i],y+dy[i],d+1});        }    }}int main(){    freopen("maze1.in","r",stdin);    freopen("maze1.out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=0;i<=m*2;i++)        scanf("%*c%[^\n]",c[i]);    memset(dis,0x3f3f3f3f,sizeof dis);    bfs();    for(int i=1;i<=2*m;i+=2)    for(int j=1;j<=2*n;j+=2)        ans=max(ans,dis[i][j]);    printf("%d\n",ans+1>>1);    return 0;}