1050.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1050 on 2006-01-18 at 02:10:13 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

const int MAX = 320;

int w, h;
char map[MAX][MAX];
queue<int> Q;

void find(double&, double&);

int main()
{
	int i, t;
	double px[MAX], py[MAX];
	char line[MAX];
	
	while(scanf("%d %d", &w, &h) != EOF && w != 0 && h != 0) {
		bool end = false;
		scanf("\n");
		for(t = 0; !end; t++) {
			for(i = 0; i < h; i++) gets(map[i]);
			find(px[t], py[t]);
			gets(line);
			if(line[0] == '=') end = true;
		}
		int T = t / 2;
		double tx = 0, ty = 0;
		for(i = 0; i < T; i++) tx += px[i+T]-px[i], ty += py[i+T]-py[i];
		double rx = ty/(T*T), ry = tx/(T*T);
		printf("%.2lf %.2lf\n", rx, ry);
	}

	return 0;
}

void find(double& x, double& y)
{
	int obj = 0, i, j;
	for(i = 0; i < h; i++)
		for(j = 0; j < w; j++)
			if(map[i][j] != '.') {
				while(!Q.empty()) Q.pop();
				Q.push((i<<8)+j); map[i][j] = '.';
				int wn = 0;
				double wx = 0, wy = 0;
				while(!Q.empty()) {
					int p = Q.front(); Q.pop(); wn++;
					int cx = p >> 8, cy = p & 255;
					wx += cx; wy += cy;
					if(cx != 0 && map[cx-1][cy] != '.') 
						map[cx-1][cy] = '.', Q.push(((cx-1)<<8)+cy);
					if(cx+1 != h && map[cx+1][cy] != '.') 
						map[cx+1][cy] = '.', Q.push(((cx+1)<<8)+cy);
					if(cy+1 != w && map[cx][cy+1] != '.') 
						map[cx][cy+1] = '.', Q.push((cx<<8)+cy+1);
					if(cy != 0 && map[cx][cy-1] != '.') 
						map[cx][cy-1] = '.', Q.push((cx<<8)+cy-1);
				}
				if(wn > obj) obj = wn, x = wx/wn, y = wy/wn;
			}
}