2211.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2211 on 2006-04-18 at 12:04:35 */ 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

const int BN = 64;
const int SN = 32;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, 
							{ 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

int w, h;

bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w; }

int main()
{
	char map[2][BN][BN];
	int s, num[2][SN];
	bool rule[SN][2][10];
	int t, T, i, j, k;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d %d %d\n", &w, &h, &s);
		memset(num, 0, sizeof(num)); memset(rule, false, sizeof(rule));
		for(i = 0; i < h; i++) {
			gets(map[0][i]);
			for(j = 0; j < w; j++)
				if(isalpha(map[0][i][j])) num[0][map[0][i][j]-'A']++, num[1][map[0][i][j]-'A']++;
		}
		char r[150]; 
		for(k = 0; k < s; k++) {
			scanf("\n"); gets(r);
			for(i = j = 0; j < 2; j++, i++)
				for(; r[i] != 0 && r[i] != '/'; i++) rule[k][j][r[i]-'0'] = true;
		}
		int turn, tu; scanf("%d", &turn);
		for(tu = 0; tu < turn; tu++) {
			int temp[SN] = { 0 };
			for(i = 0; i < h; i++)
				for(j = 0; j < w; j++) {
					int ln[SN] = { 0 }, nt = 100, nk = map[tu&1][i][j]-'A';
					for(k = 0; k < 8; k++) {
						int x = i+DIR[k][0], y = j+DIR[k][1];
						if(!legal(x, y)) continue;
						if(isalpha(map[tu&1][x][y])) ln[map[tu&1][x][y]-'A']++;
					}
					if(isalpha(map[tu&1][i][j]) && rule[nk][0][ln[nk]]) nt = nk;
					for(k = 0; k < s; k++)
						if(map[tu&1][i][j] != k+'A' && rule[k][1][ln[k]]) nt = min(nt, k);
					map[1-(tu&1)][i][j] = ((nt == 100) ? '.' : nt+'A');
					if(nt != 100) temp[nt]++;
				}
			for(i = 0; i < s; i++) {
				num[0][i] = max(num[0][i], temp[i]);
				num[1][i] = min(num[1][i], temp[i]);
			}
		}
		printf("Simulation #%d\n", t);
		for(i = 0; i < s; i++)
			printf("Species %c: At most %d live, at least %d live.\n", i+'A', num[0][i], num[1][i]);
	}
	
	return 0;
}