[BOJ 16235] 나무 재테크

백준 :: BOJ :: 16235 :: 나무 재테크

출처 : https://www.acmicpc.net/problem/16235

#include <bits/stdc++.h>

using namespace std;

struct Tr {

int i, j, a;

bool operator<(const Tr& vv) const { return a < vv.a; }

};

int N, M, K, A[11][11], arr[11][11];

int di[] = { -1,-1,-1,0,1,1,1,0 }, dj[] = { -1,0,1,1,1,0,-1,-1 };

vector <Tr> v, tv; queue<Tr> q;

inline bool chk(int i, int j) { return (i > 0 && j > 0 && i <= N && j <= N) ? true : false; }

void year() {

sort(v.begin(), v.end()); Tr t;

for (int i = 0; i < v.size(); i++) {

t = v[i];

if (arr[t.i][t.j] >= t.a) { arr[t.i][t.j] -= t.a; t.a++;  tv.push_back(t); }

else q.push(t);

}

v.swap(tv); tv.clear();

while (!q.empty()) {

t = q.front(); q.pop();

arr[t.i][t.j] += (t.a / 2);

}

for (int i = 0; i < v.size(); i++) {

if (v[i].a % 5 == 0) {

for (int d = 0; d < 8; d++) {

t = v[i]; t.i += di[d]; t.j += dj[d]; t.a = 1;

if (chk(t.i, t.j)) v.push_back(t);

}

}

}

if (K) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) arr[i][j] += A[i][j];

}

int main() {

std::ios::sync_with_stdio(false); cin.tie(0);

cin >> N >> M >> K;

for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {

cin >> A[i][j]; arr[i][j] = 5;

}

while (M--) {

Tr tmp; cin >> tmp.i >> tmp.j >> tmp.a;

v.push_back(tmp);

}

while (K--) {

year();

}

cout << v.size();

return 0;

}