## usaco Overfencing

2018年04月23日 ⁄ 综合 ⁄ 共 1744字 ⁄ 字号 评论关闭

code:

```/*
ID:yueqi
LANG:C++
*/
#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 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(){
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;
}
```