2013年12月16日 星期一

[USACO] 2-4-2 Overfencing


/*
ID: 551100k1
LANG: C++
TASK: maze1
*/
#include<stdio.h>
#include<queue>
using namespace std;
struct P{
    int x,y,add;
}in,out;
char s[205][205]={0};
int v[205][205]={0},d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
queue<P> que;
int main(){
    freopen("maze1.in","r",stdin);
    freopen("maze1.out","w",stdout);
    int n,m,i,j,ans=0;
    scanf("%d%d\n",&m,&n);
    n=n*2+1,m=m*2+1;
    for(i=1;i<=n;i++)
        gets(&s[i][1]);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(i==1 || j==1 || i==n || j==m)
                if(s[i][j]==' ')
                    que.push((P){i,j,1}),v[i][j]=1;
    while(que.size()){
        out=que.front();
        que.pop();
        if(out.add>ans) ans=out.add;
        for(i=0;i<4;i++)
        if(s[out.x+d[i][0]][out.y+d[i][1]]==' ' && v[out.x+d[i][0]][out.y+d[i][1]]==0){
            v[out.x+d[i][0]][out.y+d[i][1]]=1;
            in=out,in.x+=d[i][0],in.y+=d[i][1],in.add++;
            que.push(in);
        }
    }
    printf("%d\n",ans/2);
}

沒有留言:

張貼留言