1383.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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 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;
}