学步园

思路很简单，就是从两个出口对每个点进行一次bfs，结果各种各种问题被各种虐。。。。。

code:

/*
    ID:yueqi
    LANG:C++
    TASK:maze1
*/
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("maze1.in","r",stdin)
#define writef freopen("maze1.out","w",stdout)
const int maxn = 500;
const long long BigP=999983;
const long long  INF = 0x5fffffff;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
int x[2],y[2];
char s[210][100];
int q[20000][2],maxx,dis[2][210][100];
bool t[2][210][100];
void bfs(int x, int y, int n, int m, int h){
    int start=0,end=1;
    q[start][0] = x;
    q[start][1] = y;
    dis[h][x][y] = 1;
    t[h][x][y] = 1;
    while(start!=end){
        x=q[start][0],y=q[start][1];
        FF(i,4){
            int nx=x+dx[i],ny=y+dy[i];
            if (nx>=0&&nx<n&&ny>=0&&ny<m&&!t[h][nx][ny]&&s[nx][ny]==' '){
                q[end][0]=nx;
                q[end][1]=ny;
                dis[h][nx][ny]=dis[h][x][y]+1;
                t[h][nx][ny]=true;
                end++;
            }
        }start++;
    }
}
int main(){
    readf;writef;
    int n,m,k=0;
    scanf("%d%d",&n,&m);
    getchar();
    n=n*2+1;m=m*2+1;
    FF(i,m){
        FF(j,n){
            scanf("%c", &s[i][j]);
            if (s[i][j]==' '&&(i==0||i==m-1||j==0||j==n-1)){
                x[k] = i, y[k++] = j;
            }
        }getchar();
    }
    bfs(x[0],y[0],m,n,0);
    bfs(x[1],y[1],m,n,1);
    FF(i,m) FF(j,n) maxx=max(maxx,min(dis[0][i][j], dis[1][i][j]));
    printf("%d\n", maxx/2);
    return 0;
}