마법사 상어와 파이어스톰

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0753 ~ 0905
int dc[4] = {0, 1, 0, -1}; // 상 우 하 좌
int dr[4] = {-1, 0, 1, 0};
int N,Q,ans_sum,ans_size,L;
int board[70][70];
int t_board[70][70];
bool vis[70][70];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q;
    int num = pow(2,N);
    for(int i=1;i<=num;i++)
        for(int j=1;j<=num;j++)
            cin >> board[i][j];
    while(Q--)
    {
        cin >> L;
        int size = pow(2,L);
        /* 90도 회전 */
        for(int r=1;r<=num/size;r++)
        {
            for(int c=1;c<=num/size;c++)
            {
                int st_r = 1+(r-1)*size;
                int st_c = 1+(c-1)*size;
                /* 임시배열에 90도 회전값 저장 */
                int t_c=(st_c+size);
                for(int i=st_r;i<st_r+size;i++)
                {
                    int t_r=(st_r)-1;
                    t_c--;
                    for(int j=st_c;j<st_c+size;j++)
                        t_board[++t_r][t_c] = board[i][j];
                }
                /* 원래 배열에 다시 복사 */
                for(int i=st_r;i<st_r+size;i++)
                    for(int j=st_c;j<st_c+size;j++)
                        board[i][j] = t_board[i][j];
            }
        }
        /* 얼음 0~2개 인접해 있는 칸에 대해 얼음량-1 */
        int SUM=0;
        for(int r=1;r<=num;r++)
            for(int c=1;c<=num;c++)
            {
                if(board[r][c] == 0) continue;
                int cnt=0;
                for(int dir=0;dir<4;dir++)
                {
                    int nr = r + dr[dir];
                    int nc = c + dc[dir];
                    if(nr<1 or nc<1 or nr>num or nc>num) continue;
                    if(board[nr][nc] > 0) cnt++;
                }
                if(cnt < 3) t_board[r][c]--;
                SUM += t_board[r][c];
            }
        /* 다시 board에 복사 */
        for(int r=1;r<=num;r++)
            for(int c=1;c<=num;c++)
                board[r][c] = t_board[r][c];
        /* 가장 큰 얼음덩어리를 찾는 BFS */
        int MAX = 0;
        for(int i=1;i<=num;i++)
            fill(vis[i]+1, vis[i]+num+1, false);
        for(int r=1;r<=num;r++)
        {
            for(int c=1;c<=num;c++)
            {
                if(vis[r][c] or board[r][c] == 0) continue;
                queue<pair<int,int>> q;
                q.push({r,c});
                vis[r][c] = true;
                int cnt = 1;
                while(!q.empty())
                {
                    auto cur = q.front(); q.pop();
                    for(int dir=0;dir<4;dir++)
                    {
                        int nr = cur.first + dr[dir];
                        int nc = cur.second + dc[dir];
                        if(nr<1 or nc<1 or nr>num or nc>num) continue;
                        if(vis[nr][nc] or board[nr][nc] == 0) continue;
                        vis[nr][nc] = true;
                        cnt++;
                        q.push({nr,nc});
                    }
                }
                MAX = max(MAX, cnt);
            }
        }
        ans_size = MAX;
        ans_sum = SUM;
    }
    cout << ans_sum << '\n' << ans_size;
    return 0;
}

• 핵심
  • 각 크기마다 접근해서 90도 회전하는 것이 핵심
    : 각 좌표에 대해 st_r / st_c를 지정해서 st_r+_size / st_c+size 까지 수행해서 임시 배열 t_board에 저장