1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<stdio.h>
#include<string.h>
int max,tn,tm;
int W,H;
int flag[1200][1200];
char map[1200][1200];
int tmove[4]= {1,-1,0,0};
void dfs(int n,int m,int cnt) {
	if(max<cnt) {
		max=cnt,tn=n,tm=m;
	}
	for(int i=0; i<4; i++) {
		int moven=n+tmove[i],movem=m+tmove[(i+2)%4];
		if(moven>=0&&moven<H&&movem>=0&&movem<W&&map[moven][movem]=='.'&&!flag[moven][movem]) {
			flag[moven][movem]=1;
			dfs(moven,movem,cnt+1);
		}
	}
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&W,&H);
		getchar();
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				scanf("%c",&map[i][j]);
				if(map[i][j]=='.') {
					tn=i;
					tm=j;
				}
			}
			getchar();
		}
		max=0;
		memset(flag,0,sizeof(flag));
		flag[tn][tm]=1;
		dfs(tn,tm,0);
		memset(flag,0,sizeof(flag));
		flag[tn][tm]=1;
		dfs(tn,tm,0);
		printf("Maximum rope length is %d.\n",max);
	}
	return 0;
}