5656 벽돌깨기

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <memory>
 
using namespace std;
 
int arr[20][20];
int min_rst;
int n, w, h;
 
void dfs_ball(int num, int depth);
void dfs_block(int y, int x);
void normalize();
int count_block();
int tmp_count_block();
 
int main() {
    int t;
    scanf("%d", &t);
 
    for (int i = 1; i <= t; i++) {
        memset(arr, 0, sizeof(arr));
        min_rst = 10000000000;                
        scanf("%d %d %d", &n, &w, &h);
 
        for (int j = 1; j <= h; j++) 
            for (int k = 1; k <= w; k++)
                scanf("%d", &arr[j][k]);
                
        for (int j = 1; j <= w; j++) 
            dfs_ball(j, 1);
        
        printf("#%d %d\n", i, min_rst);
    }
}
 
void dfs_ball(int num, int depth) {        
    
    if (depth > n) {
        int tmp_rst = count_block();
 
        if (min_rst > tmp_rst)
            min_rst = tmp_rst;
    }
    else {
        int tmp_arr[20][20];
        memcpy(tmp_arr, arr, sizeof(arr));
 
        for (int i = h; i >= 0; i--) 
            if (arr[i][num] == 0) {                
                dfs_block(i + 1, num);
                break;
            }
        
        normalize();
 
        for (int i = 1; i <= w; i++) 
            dfs_ball(i, depth + 1); 
        
        memcpy(arr, tmp_arr, sizeof(tmp_arr));
    }
}
 
void dfs_block(int y, int x) {
    int power = arr[y][x] - 1;
    arr[y][x] = 0;
 
    for (int i = x - power; i <= x + power; i++) {
        if (i <= 0 || i > w)
            continue;
 
        if (arr[y][i] > 1)
            dfs_block(y, i);
        else
            arr[y][i] = 0;
    }
 
    for (int i = y - power; i <= y + power; i++) {
        if (i <= 0 || i > h)
            continue;
 
        if (arr[i][x] > 1)
            dfs_block(i, x);
        else
            arr[i][x] = 0;
    }
}
 
void normalize() {
    int tmp_arr[20][20] = { 0 };
 
    for (int i = 1; i <= w; i++) {    
        int idx = h;
        for (int j = h; j >= 1; j--) {
            if (arr[j][i] > 0) {
                tmp_arr[idx][i] = arr[j][i];
 
                idx--;
            }    
        }
    }
 
    memcpy(arr, tmp_arr, sizeof(tmp_arr));
}
 
int count_block() {
    int cnt = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (arr[i][j] > 0)
                cnt++;
        }
    }
 
    return cnt;
}
 
int tmp_count_block() {
    int cnt = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {        
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
 
    return cnt;
}

아오 머리아퍼

그래도 제 시간 안에는 풀었네