나무 재테크 C++

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

16235번: 나무 재테크

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 12;
int n, m, k;
struct MOVE { int x, y; };
MOVE mv[8] = { {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} };
int map[MAX][MAX];
vector<int> tree[MAX][MAX];
struct INFO { int x, y, z; };
vector<INFO> dtree;
int plus_tree[MAX][MAX];

void Spring() {
    dtree.clear();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (tree[i][j].size() == 1) {
                if (map[i][j] >= tree[i][j][0]) {
                    map[i][j] -= tree[i][j][0];
                    tree[i][j][0] += 1;
                }
                else {
                    dtree.push_back({ i,j,tree[i][j][0] });
                    tree[i][j].clear();
                }
            }
            else if (tree[i][j].size() > 1) {
                sort(tree[i][j].begin(), tree[i][j].end());
                vector<int> tmp;
                for (int k = 0; k < tree[i][j].size(); k++) {
                    if (map[i][j] >= tree[i][j][k]) {
                        map[i][j] -= tree[i][j][k];
                        tree[i][j][k] += 1;
                        tmp.push_back(tree[i][j][k]);
                    }
                    else {
                        dtree.push_back({ i,j,tree[i][j][k] });
                    }
                }
                tree[i][j] = tmp;
            }
        }
    }
}

void Summer() {
    for (int i = 0; i < dtree.size(); i++) {
        int age = dtree[i].z / 2;
        map[dtree[i].x][dtree[i].y] += age;
    }
}

void Fall() {
    vector<int> tmp_tree[MAX][MAX];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            tmp_tree[i][j] = tree[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < tree[i][j].size(); k++) {
                if (tree[i][j][k] != 0 && tree[i][j][k] % 5 == 0) {
                    for (int kk = 0; kk < 8; kk++) {
                        int movei = i + mv[kk].x;
                        int movej = j + mv[kk].y;

                        if (movei > 0 && movei <= n && movej > 0 && movej <= n) {
                            tmp_tree[movei][movej].push_back(1);
                        }
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            tree[i][j] = tmp_tree[i][j];
        }
    }
}

void Winter() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] += plus_tree[i][j];
        }
    }
}

int main(void) {
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = 5;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> plus_tree[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        tree[x][y].push_back(z);
    }

    for (int testcase = 0; testcase < k; testcase++) {
        Spring();
        Summer();
        Fall();
        Winter();
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (tree[i][j].size() > 0) {
                answer += tree[i][j].size();
            }
        }
    }
    cout << answer << endl;
}