找出两个迷宫的出口，然后分别进行dfs，求出到每一个点的最短距离。
然后对每一个点，求到最短的那个出口的距离，然后再求这个值的最大值即可。
找出口写得比较繁琐。
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("maze1.in");
ofstream fout("maze1.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
char maze[2*100+1][2*38+1];
bool visited[100][38];
int shortest1[100][38];
int shortest2[100][38];
bool get_first;
int exit1r,exit1c;
int exit2r,exit2c;
int w,h;
struct queue_node{
int i,j,depth;
queue_node(int i,int j,int depth){
this->i = i;
this->j = j;
this->depth = depth;
}
};
void bfs(int i,int j,int shortest[100][38])
{
queue<queue_node>q;
q.push(queue_node(i,j,1));
while(!q.empty()){
queue_node node = q.front();
q.pop();
if(visited[node.i][node.j])
continue;
visited[node.i][node.j] = true;
shortest[node.i][node.j] = node.depth;
if(node.i!=0&&maze[2*node.i][2*node.j+1]==' '){
q.push(queue_node(node.i-1,node.j,node.depth+1));
}
if(node.i!=h-1&&maze[2*node.i+2][2*node.j+1]==' '){
q.push(queue_node(node.i+1,node.j,node.depth+1));
}
if(node.j!=0&&maze[2*node.i+1][2*node.j]==' '){
q.push(queue_node(node.i,node.j-1,node.depth+1));
}
if(node.j!=w-1&&maze[2*node.i+1][2*node.j+2]==' '){
q.push(queue_node(node.i,node.j+1,node.depth+1));
}
}
}
void solve()
{
in>>w>>h;
for(int i=0;i<2*h+1;++i)
for(int j=0;j<2*w+1;++j){
do{
in.get(maze[i][j]);
}while(maze[i][j]=='\n');
if((i==0||i==2*h||j==0||j==2*w)&&maze[i][j]==' '){
if(!get_first){
if(i==2*h)
exit1r = h-1;
else
exit1r = i/2;
if(j==2*w)
exit1c = w-1;
else
exit1c = j/2;
get_first = true;
}else{
if(i==2*h)
exit2r = h-1;
else
exit2r = i/2;
if(j==2*w)
exit2c = w-1;
else
exit2c = j/2;
}
}
}
memset(visited,0,sizeof(visited));
bfs(exit1r,exit1c,shortest1);
memset(visited,0,sizeof(visited));
bfs(exit2r,exit2c,shortest2);
int res = INT_MIN;
for(int i=0;i<h;++i)
for(int j=0;j<w;++j){
res = max(res, min(shortest1[i][j],shortest2[i][j]) );
}
out<<res<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}