[BOJ]16235 나무 재테크.cpp

// #16235 나무재테크


//K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
int dir[8][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 }, {1,1}, { -1,1 }, { 1,-1 }, { -1,-1 } };
int n, m,k;//사이즈,나무의개수,k년
int A[11][11];//겨울마다 줄 양분
int map[11][11];
int cnt;//살아있는 나무의 개수
deque <int> tree[11][11];

void simul() {
	//이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.
	
	//봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
	//각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
	//하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
	//만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 
	//양분을 먹지 못하고 즉시 죽는다.
    
    //여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
	//각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.
	//소수점 아래는 버린다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int sz = tree[i][j].size();
			if (sz == 0)continue;
			int keepidx = 0;
			bool once = true;
			//cout << "x " << i << " y " << j << " sz " << sz << " map[x][y] " << map[i][j] << endl;
			for (int t = 0; t < sz; t++) {
				if (once&&map[i][j] >= tree[i][j][t]) {
					map[i][j] -= tree[i][j][t];
					tree[i][j][t]++;
					keepidx++;
					
				}
				else {
					map[i][j] += tree[i][j][t]/2;
					once = false;
				}
			}

			//cout << "keepidx " << keepidx << endl;
			
			tree[i][j].erase(tree[i][j].begin() + keepidx, tree[i][j].end());
			cnt -= (sz - keepidx);
		}
	}
	

	//가을에는 나무가 번식한다.번식하는 나무는 나이가 5의 배수이어야 하며, 
	//인접한 8개의 칸에 나이가 1인 나무가 생긴다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int sz = tree[i][j].size();
			for (int t = 0; t < sz; t++) {
				if (tree[i][j][t] % 5 == 0) {
					for (int d = 0; d < 8; d++) {
						int nx = i + dir[d][0], ny = j + dir[d][1];
						if (nx <= 0 || ny <= 0 || nx > n || ny > n)continue;
						tree[nx][ny].push_front(1);
						cnt++;
					}
				}
			}
		}
	}

	//겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
	//각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			map[i][j] += A[i][j];
		}
	}

}

int main() {

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> A[i][j];
			map[i][j] = 5;
		}
	}
	int x, y, age;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> age;
		tree[x][y].push_front(age);
		cnt++;
	}

	for (int i = 0; i < k; i++) {
		simul();
	}
	cout << cnt << endl;
}