Google Code Jam 2010:Round2 Problem C. Bacteria small

セル・オートマトンみたいな問題。

Small程度のデータセットなら実行例のようにシミュレーション可能。
バクテリアの初期位置は100マス×100マスの範囲内。この範囲の外では、北と西に同時にバクテリアが存在することは無いから、この中だけでシュミレーションをすればOK.

で、Large問題がこんな簡単な方法で解けるはずがなく・・・うん、諦めてまたあとで考えよう。

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define rep(i,a,b) for(int i=a;i<b;i++)

using namespace std;

#define MAX 110

char map[MAX][MAX];

int solve(int no)
{
	int R;
	cin >> R;
	
	rep(i,0,MAX) {
		rep(j,0,MAX) {
			map[i][j] = 0;
		}
	}
	
	rep(i,0,R) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		rep(x,x1,x2+1) {
			rep(y, y1, y2+1) {
				map[x][y] = 1;
			}
		}
	}
	
	int cnt = 0;
	while(1) {
		int flag = 0;
		for(int x=MAX-1;x>0;x--) {
			for(int y=MAX-1;y>0;y--) {
				if(map[x][y]) {
					flag = 1;
					if(!map[x-1][y] && !map[x][y-1]) {
						map[x][y] = 0;
					}
				} else {
					if(map[x-1][y] && map[x][y-1]) {
						map[x][y] = 1;
					}
				}
			}
		}
		if(!flag) break;
		cnt++;
	}
	
	cout << "Case #" << no << ": " << cnt << endl;
}

int main()
{
	int T;
	cin >> T;
	rep(no,0,T) {
		solve(no+1);
	}
	return 0;
}