[BOJ] 16235. 나무 재테크

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define p pair<int,int>
using namespace std;


int dx[] = {0,0,1,-1,-1,-1,1,1};
int dy[] = {1,-1,0,0,-1,1,1,-1};


int bun[10][10];
int add_bun[10][10];


int n,m,k;

struct Node{
    int value;
    int alive;
    Node(int a,int b): value(a), alive(b) {};
};

vector<Node> map[10][10];
vector<Node> v;

void print(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            
            if(map[i][j].size() == 0 )
                cout << " " << " ";
            else
                cout << map[i][j].front().value << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void print_size(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            
            if(map[i][j].size() == 0 )
                cout << " " << " ";
            else
                cout << map[i][j].size() << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void print_bun(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << bun[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

/*
 내림차순 정렬을 위한 compare 함수
 */
bool compare(Node &p1, Node &p2){
    return p1.value > p2.value;
}

bool inRange(int x, int y){
    if( x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}


void spring_summer(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int size = (int) map[i][j].size();
            if( size == 0 )
                continue;
            
            v.clear();
            /*
             봄 작업
             */
            sort(map[i][j].begin(), map[i][j].end(), compare);
            for(int k=size-1; k>=0; k--){
                /*
                 내림차순 정렬을 했기 때문에
                 가장 마지막 부분부터 참조한다.
                 */
                Node top = map[i][j][k];
                map[i][j].pop_back();
                if(bun[i][j] >= top.value){
                    bun[i][j] -= top.value;
                    v.push_back( Node(top.value + 1, 1 ) );
                }
                else{
                    v.push_back( Node(top.value , 0 ));
                }
            }
            
            /*
             여름 작업
             alive = 1 이면 다시 map에 더해주고
             alive = 0 이면 양분(=bun)으로 더해준다.
             */
            for(int k=0; k<size; k++){
                if(v[k].alive == 0){
                    bun[i][j] += v[k].value / 2;
                }
                else{
                    map[i][j].push_back( v[k]  );
                }
            }
            
        } // end of for j
    } // end of for i
}

void fall_winter(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            /*
             겨울 작업
             */
            bun[i][j] += add_bun[i][j];
            int size = (int) map[i][j].size();
            if( size == 0 )
                continue;
            
            int nx;
            int ny;
            /*
             가을 작업
             */
            for(int k=0; k<size; k++){
                Node top = map[i][j][k];
                if(top.value % 5 == 0){
                    for(int q=0; q<8; q++){
                        nx = i + dx[q];
                        ny = j + dy[q];
                        if(! inRange(nx, ny)) continue;
                        map[nx][ny].push_back(Node(1,1));
                    } // end of for q
                } // end of if
            } // end of for k
        } // end of for j
    } // end of for i
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> k;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            bun[i][j] = 5;
            cin >> add_bun[i][j];
        }
    }
    
    for(int i=0; i<m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        map[a-1][b-1].push_back( Node(c,1) );
    }
    
    while (k--) {
        spring_summer();
        fall_winter();
//        print();
//        print_size();
//        print_bun();
    }
    
    int ans = 0;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int size = (int) map[i][j].size();
            ans += size;
        }
    }
    
    cout << ans << endl;
    return 0;
}