백준 23289번 : 온풍기 안녕! - 시뮬레이션 C++

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

23289번: 온풍기 안녕!

문제를 해결하기 위해서는 상당한 기합이 필요하다..

 

 

#include <bits/stdc++.h>

using namespace std;

int chocolate, R, C, K, W, Map[21][21];
bool Wall[21][21][4];
vector<pair<int, int> > toCheck;
vector<tuple<int, int, int> > hotAirBlower;

void warmAir() {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};

    //hd, x, y
    int nextDir[4][2][3] = {
            {{-1, 0,  1},  {1,  1,  1}},
            {{-1, 0,  1},  {-1, -1, -1}},
            {{-1, -1, -1}, {1,  0,  -1}},
            {{1,  1,  1},  {1,  0,  -1}}
    };

    for (auto h: hotAirBlower) {
        int addWarm[21][21];
        memset(addWarm, 0, sizeof(addWarm));

        auto [hx, hy, hd] = h;
        queue<pair<int, int> > Q;
        int stx = hx + dx[hd];
        int sty = hy + dy[hd];

        Q.push({stx, sty});
        addWarm[stx][sty] = 5;
        while (!Q.empty()) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            if (addWarm[x][y] == 1) continue;
            for (int i = 0; i < 3; i++) {
                int nx = x + nextDir[hd][0][i];
                int ny = y + nextDir[hd][1][i];

                if (nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
                if (addWarm[nx][ny]) continue;
                //사이에 벽이 있는 경우
                if (abs(nx - x) && abs(ny - y)) { //대각선
                    if (hd == 0) {
                        if (nx - x > 0) {
                            if (Wall[x][y][2] || Wall[nx][ny][3]) continue;
                        } else {
                            if (Wall[x][y][0] || Wall[nx][ny][3]) continue;
                        }
                    } else if (hd == 1) {
                        if (nx - x > 0) {
                            if (Wall[x][y][2] || Wall[nx][ny][1]) continue;
                        } else {
                            if (Wall[x][y][0] || Wall[nx][ny][1]) continue;
                        }
                    } else if (hd == 2) {
                        if (ny - y > 0) {
                            if (Wall[x][y][1] || Wall[nx][ny][2]) continue;
                        } else {
                            if (Wall[x][y][3] || Wall[nx][ny][2]) continue;
                        }
                    } else {
                        if (ny - y > 0) {
                            if (Wall[x][y][1] || Wall[nx][ny][0]) continue;
                        } else {
                            if (Wall[x][y][3] || Wall[nx][ny][0]) continue;
                        }
                    }
                } else {
                    if (nx - x == 1 && Wall[x][y][2]) continue;
                    else if (nx - x == -1 && Wall[x][y][0])continue;
                    else if (ny - y == 1 && Wall[x][y][1]) continue;
                    else if (ny - y == -1 && Wall[x][y][3]) continue;
                }
                addWarm[nx][ny] = addWarm[x][y] - 1;

                Q.push({nx, ny});
            }
        }

        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                Map[i][j] += addWarm[i][j];
            }
        }

    }
}

void temperatureControl() {
    int tmp[21][21];
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};


    for (int x = 1; x <= R; x++) {
        for (int y = 1; y <= C; y++) {
            int curTemper = Map[x][y];
            int sum = 0;
            int minus = 0;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
                //벽
                if (nx - x == 1 && Wall[x][y][2]) continue;
                else if (nx - x == -1 && Wall[x][y][0])continue;
                else if (ny - y == 1 && Wall[x][y][1]) continue;
                else if (ny - y == -1 && Wall[x][y][3]) continue;

                if (Map[nx][ny] > Map[x][y]) {
                    sum += abs(Map[nx][ny] - Map[x][y]) / 4;
                } else if (Map[nx][ny] < Map[x][y]) {
                    minus += abs(Map[nx][ny] - Map[x][y]) / 4;
                }
            }
            tmp[x][y] = curTemper + sum - minus;
        }
    }
    swap(tmp, Map);
}

void temperatureMinus() {
    for (int i = 1; i <= R; i++) {
        if (Map[i][1]) Map[i][1]--;
        if (Map[i][C]) Map[i][C]--;
    }
    for (int i = 2; i <= C-1; i++) {
        if (Map[1][i]) Map[1][i]--;
        if (Map[R][i]) Map[R][i]--;
    }
}

bool endCheck() {
    if(chocolate > 100) return true;
    for (auto a: toCheck) {
        if (Map[a.first][a.second] < K) return false;
    }
    return true;
}

void Input() {
    cin >> R >> C >> K;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            int num;
            cin >> num;
            if (num == 5) {
                toCheck.push_back({i, j});
            } else if (num > 0) {
                hotAirBlower.push_back({i, j, num - 1});
            }
        }
    }
    cin >> W;
    for (int i = 1; i <= W; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        if (t == 0) {
            Wall[x][y][0] = 1;
            Wall[x - 1][y][2] = 1;
        } else {
            Wall[x][y][1] = 1;
            Wall[x][y + 1][3] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();

    do {
        warmAir();
        temperatureControl();
        chocolate++;
        temperatureMinus();
    } while (!endCheck());

    cout << ((chocolate > 100) ? 101 : chocolate) << '\n';

    return 0;
}