1030.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1030 on 2005-12-20 at 20:25:12 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1024;

char map[MAX][MAX];
int stack[MAX*MAX], d[MAX][MAX];
int len[MAX][MAX];
int w, h;

int degree(int, int);

int main()
{
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d\n", &w, &h);
		for(i = 0; i < h; i++) {
			gets(map[i]);
		}
		memset(len, 0, sizeof(len));
		int top = 0;
		for(i = 0; i < h; i++) {
			for(j = 0; j < w; j++) {
				d[i][j] = degree(i, j);
				if(d[i][j] == 1) {
					stack[top++] = i * w + j;
				}
			}
		}
		int longest = 0;
		while(top > 1) {
			i = stack[top-1] / w, j = stack[--top] % w;
			int c, r;
			if(i != 0 && map[i-1][j] == '.') c = i-1, r = j;
			else if(i != h && map[i+1][j] == '.') c = i+1, r = j;
			else if(j != 0 && map[i][j-1] == '.') c = i, r = j-1;
			else c = i, r = j+1;
			longest = max(longest, len[i][j]+len[c][r]+1);
			len[c][r] = max(len[i][j]+1, len[c][r]);
			d[c][r]--, map[i][j] = '#';
			if(d[c][r] == 1) stack[top++] = c * w + r;
		}
		printf("Maximum rope length is %d.\n", longest);
	}
	
	return 0;
}

int degree(int i, int j)
{
	int de = 0;
	if(map[i][j] == '#') return 0;
	if(i != 0 && map[i-1][j] == '.') de++;
	if(i != h && map[i+1][j] == '.') de++;
	if(j != 0 && map[i][j-1] == '.') de++;
	if(j != w && map[i][j+1] == '.') de++;
	return de;
}