floodfill
/**//*
ID: lorelei3
TASK: maze1
LANG: C++
*/
#include<stdio.h>
const int dx1[4] = 
{1, -1, 0, 0};
const int dy1[4] = {0, 0, 1, -1};
const int dx2[4] = {2, -2, 0, 0};
const int dy2[4] = {0, 0, 2, -2};
const int INF = 999999;
bool map[250][250];
int w,h;
int f[3][250][250];
int x[3],y[3];
inline int min(int a, int b){
return a<b? a: b;
}
void floodfill(int e, int x, int y){
int x1,y1,x2,y2;
for(int i=0; i<4; ++i){
x1=x+dx1[i]; y1=y+dy1[i];
x2=x+dx2[i]; y2=y+dy2[i];
if(x2>0 && x2<=2*h+1 && y2>0 && y2<=2*w+1)
if(map[x1][y1]&&map[x2][y2]){
if(f[e][x2][y2] > f[e][x][y]+1){
f[e][x2][y2] = f[e][x][y]+1;
floodfill(e, x2, y2);
}
}
}
return ;
}
int main(){
char ch;
int i,j,k=1;
int ans=0;
freopen("maze1.in","r",stdin);
freopen("maze1.out","w",stdout);
scanf("%d%d",&w,&h);
getchar();
for(i=1; i<=2*h+1; ++i){
for(j=1; j<=2*w+1; ++j){
scanf("%c", &ch);
if(ch==' '){
map[i][j]=true;
if(i==1) { x[k]=2; y[k]=j; k++; }
if(i==2*h+1){ x[k]=2*h; y[k]=j; k++; }
if(j==1) { x[k]=i; y[k]=2; k++; }
if(j==2*w+1){ x[k]=i; y[k]=2*w; k++; }
}
}
getchar();
}
for(i=1; i<=2*h+1; ++i)
for(j=1; j<=2*w+1; ++j){
f[1][i][j] = INF;
f[2][i][j] = INF;
}
f[1][x[1]][y[1]]=1;
f[2][x[2]][y[2]]=1;
floodfill(1, x[1], y[1]);
floodfill(2, x[2], y[2]);
for(i=1; i<=2*h+1; ++i)
for(j=1; j<=2*w+1; ++j)
if((!(i&1)) && (!(j&1))){
int tmp = min(f[1][i][j], f[2][i][j]);
if(tmp>ans)
ans = tmp;
}
printf("%d\n",ans);
return 0;
}
posted on 2010-12-09 22:42
小阮 阅读(404)
评论(0) 编辑 收藏 引用 所属分类:
USACO