随笔-141  评论-9  文章-3  trackbacks-0
floodfill

/*
ID: lorelei3
TASK: maze1
LANG: C++
*/


#include
<stdio.h> 


const int dx1[4= {1-100}
const int dy1[4= {001-1}
const int dx2[4= {2-200};
const int dy2[4= {002-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 小阮 阅读(408) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理