找出兩個(gè)迷宮的出口，然后分別進(jìn)行dfs，求出到每一個(gè)點(diǎn)的最短距離。
然后對(duì)每一個(gè)點(diǎn)，求到最短的那個(gè)出口的距離，然后再求這個(gè)值的最大值即可。
找出口寫(xiě)得比較繁瑣。
#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;
}