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; }