1075.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1075 on 2006-02-12 at 04:45:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 64;
const int DIR[4][2] = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };

int wall[MAX][MAX], room[MAX][MAX], large;
int w, h, rn, size[MAX*MAX];

void fillRoom();

int main()
{
	int i, j, k;
	
	while(scanf("%d %d", &w, &h) != EOF) {
		for(i = 0; i < h; i++)
			for(j = 0; j < w; j++) scanf("%d", &wall[i][j]);
		fillRoom();
		printf("%d\n%d\n", rn, large); large = 0;
		int bx, by; char d;
		for(j = 0; j < w; j++)
			for(i = h-1; i >= 0; i--)
				for(k = 1; k <= 2; k++) {
					if(i == 0 && k == 1) continue;
					if(j == w-1 && k == 2) continue;
					int x = i+DIR[k][0], y = j+DIR[k][1];
					if(room[i][j] != room[x][y] && large < size[room[i][j]]+size[room[x][y]])
						large = size[room[i][j]]+size[room[x][y]], bx = i, by = j, d = (k == 1) ? 'N' : 'E';
				}
		printf("%d\n%d %d %c\n\n", large, bx+1, by+1, d);
	}
	
	return 0;
}

void fillRoom()
{
	int i, j, k, stack[MAX*MAX];
	memset(room, -1, sizeof(room)); large = rn = 0;
	for(i = 0; i < h; i++)
		for(j = 0; j < w; j++)
			if(room[i][j] == -1) {
				int top = 0; size[rn] = 1;
				stack[top++] = (i << 6) | j; room[i][j] = rn;
				while(top > 0) {
					int p = stack[--top], x = p>>6, y = p&63;
					for(k = 0; k < 4; k++) {
						int cx = x+DIR[k][0], cy = y+DIR[k][1];
						if(((wall[x][y]>>k)&1) == 0 && room[cx][cy] == -1)
							{ room[cx][cy] = rn; size[rn]++; stack[top++] = (cx << 6) | cy; }
					}
				}
				large = max(large, size[rn++]);
			}
}