Poj Solution 1383

http://poj.org/problem?id=1383

#include"stdio.h"
#include"memory.h"


char map[1100][1100];
bool sign[1100][1100];
int max,bx,by,n,m;

void init_sign()
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        sign[i][j]=0;
}

void init()
{
    scanf("%d %d",&m,&n);
    for(int i=0;i<n;i++)
        scanf("%s",map[i]);
}
inline int inmap(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<m;
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

void search(int x,int y,int floor)
{
    int xx,yy;
    sign[x][y]=1;

    if(floor>max)
    {
        max=floor;
        bx=x,by=y;
    }

    for(int i=0;i<4;i++)
    {
        if(inmap(xx=x+dx[i],yy=y+dy[i])&&!sign[xx][yy]&&map[xx][yy]=='.')
            search(xx,yy,floor+1);
    }
}

void doit()
{
    int x,y;
    for(x=0;x<n;x++)
    for(y=0;y<m;y++)
        if(map[x][y]=='.')goto loop;

    max=0;
    return;
loop:
    max=-1;
    init_sign();
    search(x,y,0);

    max=-1;
    init_sign();
    search(bx,by,0);
    return;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        doit();
        printf("Maximum rope length is %d.n",max);
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *