백준 20058번 : 마법사 상어와 파이어스톰 - 구현, 시뮬레이션 C++

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

20058번: 마법사 상어와 파이어스톰

#include <bits/stdc++.h>

using namespace std;

int N,rows, Q,L, A[64][64];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void TurnBox(int x, int y, int len){
    int retBox[len][len];

    for(int i=0; i<len; i++) {
        for (int j = 0; j < len; j++) {
            retBox[j][len-1-i] = A[x+i][y+j];
        }
    }

    for(int i=0; i<len; i++) {
        for (int j = 0; j < len; j++) {
            A[x+i][y+j] = retBox[i][j];
        }
    }

}


void Turn(int _L){
    int box = pow(2,N) / pow(2, _L);
    int len = pow(2,_L);

    for(int i=0; i<box ;i++){
        for(int j=0; j<box; j++) {
            int x = i*len;
            int y = j*len;

            TurnBox(x,y,len);
        }
    }
}

void Melt(){
    vector<pair<int,int> > willMelt;

    for(int i=0; i<rows; i++){
        for(int j=0; j<rows; j++){
            int cnt = 0;
            if(A[i][j]==0) continue;
            for(int k=0; k<4; k++){
                int nx = i + dx[k];
                int ny= j +dy[k];
                if(nx<0||nx>=rows||ny<0||ny>=rows) continue;
                if(A[nx][ny] > 0) cnt++;
            }
            if(cnt <3){
                willMelt.push_back({i,j});
            }
        }
    }

    for(int i=0; i<willMelt.size();i++){
        A[willMelt[i].first][willMelt[i].second]--;
    }
}

void Round(int _L){
    Turn(_L);
    Melt();
}


void Input();
int Count(){
    int sum = 0;
    for(int i=0; i<rows; i++){
        for(int j=0; j<rows; j++){
            sum += A[i][j];
        }
    }
    return sum;
}

int getMax(){
    bool ch[64][64] = {0};
    int ans = 0;
    queue<pair<int,int> > Q;

    for(int i=0; i<rows; i++){
        for(int j=0; j<rows; j++){
            if(!ch[i][j] && A[i][j]>0){
                ch[i][j] = 1;
                int cnt = 1;
                Q.push({i,j});

                while(!Q.empty()){
                    auto cur = Q.front(); Q.pop();

                    for(int k=0; k<4; k++){
                        int nx = cur.first + dx[k];
                        int ny= cur.second +dy[k];
                        if(nx<0||nx>=rows||ny<0||ny>=rows) continue;
                        if(ch[nx][ny] || A[nx][ny]==0) continue;
                        Q.push({nx,ny});
                        ch[nx][ny] = 1;
                        cnt++;

                    }
                }

                ans = max(ans, cnt);
            }
        }
    }


    return ans;
}

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

    Input();
    cout << Count() << '\n';
    cout << getMax() << '\n';

}

void Input() {
    cin >> N >> Q;
    rows = pow(2,N);
    for(int i=0; i<rows; i++){
        for(int j=0; j<rows; j++){
            cin >> A[i][j];
        }
    }
    for(int i=0; i<Q; i++){
        cin >> L;
        Round(L);
    }
}