SWEA 5656. 벽돌 깨기 (C++)

요약

map_block 정리를 해줘야 함.

---

문제

게임의 규칙은 다음과 같다.
① 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.
② 벽돌은 숫자 1 ~ 9 로 표현되며,
구슬이 명중한 벽돌은 상하좌우로 ( 벽돌에 적힌 숫자 - 1 ) 칸 만큼 같이 제거된다.
③ 제거되는 범위 내에 있는 벽돌은 동시에 제거된다.
④ 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.


[제약 사항]
1. 1 ≤ N ≤ 4
2. 2 ≤ W ≤ 12
3. 2 ≤ H ≤ 15

[입력]
각 테스트 케이스의 첫 번째 줄에는 N, W, H 가 순서대로 공백을 사이에 두고 주어지고,
다음 H 줄에 걸쳐 벽돌들의 정보가 1 줄에 W 개씩 주어진다.

[출력]
남은 벽돌의 수를 구하여라.

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
  
using namespace std;
  
struct STATUS {
    int r; int c;
    int explode;
};
  
#define MAX_W (12)
#define MAX_H (15)
  
int map_block[MAX_H][MAX_W];
  
int N, C, R;
int sol;
queue<STATUS> q;
int total_cnt;
  
  
void Input_Data(void){
    cin >> N >> C >> R;
    total_cnt = 0;
    for (int r = 0; r < R;r++) {
        for (int c = 0; c < C;c++) {
            cin >> map_block[r][c];
            if (map_block[r][c]) total_cnt++;
        }
    }
}
  
void Init(void) {
    sol = 0;
}
  
void Copy(int (&dest)[MAX_H][MAX_W], int(&src)[MAX_H][MAX_W]) {
    for (int r = 0; r < R; r++) {
        copy(src[r], src[r] + C, dest[r]);
    }
}
  
int Check_Row(int c) {
    for (int r = 0; r < R;r++) {
        if (map_block[r][c]) return r;
    }
    return -1;
}
  
int Brake_Block(int sr, int sc) {
    static int dr[] = { 0, 0, 1,-1};
    static int dc[] = { 1,-1, 0, 0};
    int cnt = 1;
    q.push({ sr,sc,map_block[sr][sc]-1 });
    map_block[sr][sc] = 0;
      
    while (!q.empty()) {
        STATUS data = q.front(); q.pop();
          
        for (int i = 0; i < 4;i++) {
            for (int go = 1; go <= data.explode;go++) {
                STATUS ndata;
                ndata.r = data.r + go * dr[i];
                ndata.c = data.c + go * dc[i];
                if (0 > ndata.r || ndata.r >= R) break;
                if (0 > ndata.c || ndata.c >= C) break;
                if (map_block[ndata.r][ndata.c] == 0) continue;
                cnt++;
                ndata.explode = map_block[ndata.r][ndata.c]-1;
                map_block[ndata.r][ndata.c] = 0;
                if (ndata.explode) q.push(ndata);
            }
        }
    }
  
    // map_block 정리
    for (int c = 0; c < C;c++) {
        int space = R; int block = -1;
        for(;;){
            space--; 
            while (space >= 0 && map_block[space][c]) space--;
            if (space < 0) break;
            if (block == -1) block = space - 1;
            else block--;
            while (block >= 0 && map_block[block][c] == 0) block--;
            if (block < 0) break;
            map_block[space][c] = map_block[block][c];
            map_block[block][c] = 0;
        }
    }
    return cnt;
}
  
void DFS(int n, int sum_block) {
    if (sol < sum_block) sol = sum_block;
    if (n >= N) return;
  
    int back[MAX_H][MAX_W];
      
    Copy(back, map_block);
    for (int c = 0; c < C;c++) {
        int r = Check_Row(c);
        if (r == -1) continue;
        int block = Brake_Block(r, c);
        DFS(n + 1, sum_block + block);
        Copy(map_block, back);
    }
}
  
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int T;
    cin >> T;
    for (int t = 1; t <= T;t++) {
        Input_Data();
        Init();
  
        DFS(0, 0);
  
        printf("#%d %d\n",t,(total_cnt - sol));
        //cout << '#' << t << ' ' << (total_cnt - sol) << '\n';
    }
    return 0;
}