[ZOJ 3304 Prison Break]BFS、模拟、种子染色法

【题目大意】

如果把P视作不能去的区域，哪个人不能通过上下左右走到达牢房边缘的话，直接就变成Ghost

然后在剩下的人里，找最大的上下左右对角线连通的连通块。

【算法分析】

一开始处理Ghost的话，从牢房边缘bfs进来，如果不能到达某个P，他就死了。

然后剩下的就是种子染色法了。

【CODE】

#include #include int m,n,lx[1111111],ly[1111111],ans,head,tail;
char map[1111][1111];
bool v[1111][1111];

inline void expand1(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty]) return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void getghost(){
    head=0; tail=0;
    for (int i=1;i<=m;i++){
        tail++;
        lx[tail]=i;
        ly[tail]=0;
        tail++;
        lx[tail]=i;
        ly[tail]=n+1;
    }   
    for (int i=1;i<=n;i++){
        tail++;
        lx[tail]=0;
        ly[tail]=i;
        tail++;
        lx[tail]=m+1;
        ly[tail]=i;
    }
    while (head        head++;
        if (map[lx[head]][ly[head]]==’P’ && lx[head]>0 && lx[head]<=m && ly[head]>0 && ly[head]<=n)
          continue;
        expand1(lx[head]-1,ly[head]);
        expand1(lx[head]+1,ly[head]);
        expand1(lx[head],ly[head]-1);
        expand1(lx[head],ly[head]+1);
    }   
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          map[i][j]=’G’;
}

inline void expand(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty] || map[tx][ty]!='P') return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void bfs(int sx,int sy){
    head=0,tail=1;
    lx[1]=sx; ly[1]=sy;
    v[sx][sy]=true;
    while (head        head++;
        expand(lx[head]-1,ly[head]);
        expand(lx[head]+1,ly[head]);
        expand(lx[head],ly[head]-1);
        expand(lx[head],ly[head]+1);
        expand(lx[head]-1,ly[head]-1);
        expand(lx[head]-1,ly[head]+1);
        expand(lx[head]+1,ly[head]-1);
        expand(lx[head]+1,ly[head]+1);
    }   
    if (tail>ans) ans=tail;
}   

void solve(){
    memset(map,’P’,sizeof(map));
    memset(v,false,sizeof(v));
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        for (map[i][j]=getchar();map[i][j]==’ ‘ || map[i][j]==’n’;map[i][j]=getchar());
    getghost();
    memset(v,false,sizeof(v));
    ans=0;
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          bfs(i,j);
    printf("%dn",ans);
}   

int main(){
    while (scanf("%d%d",&m,&n)!=EOF) solve();
    return 0;   
}