시뮬레이션 (완전탐색) 문제이다.
가로 길이가 W인 벽돌에 최대 N번 구슬을 쐈을 때 남은 벽돌의 수를 비교하여 가장 적은 수를 출력해야 한다.
문제의 핵심은 완전탐색을 진행하면서 map을 가지고 가는 것이다.
map을 2차원 배열 형식으로 선언했기 때문에 넘겨 받은 함수에서 해당 map을 사용할 때 유의해야 한다.
따라서 dfs 함수 내에서 newmap을 선언하여 넘겨 받은 map을 복사하여 사용하고 또 넘겨주었다.
구슬은 현재 쏘고자 하는 위치에서 가장 위쪽에 위치한 벽돌에 부딪힌다.
구슬이 명중한 벽돌은 상하좌우로 (벽돌에 적힌 숫자 -1) 만큼 같이 제거된다.
이 과정은 queue를 사용하여 구현, 상하좌우로 제거 시 숫자가 1보다 클 때만 queue에 넣었다.
벽돌이 제거된 이후에는 남은 벽돌들을 아래로 끌어내려야 한다.
만약 현재 위치에서 깨트릴 수 있는 벽돌이 없다면, 남은 벽돌의 수를 센다.
이때 쏠 수 있는 구슬의 수가 남아 있을 경우 탐색을 계속해서 진행한다.
N번 구슬을 쏜 경우, 남은 벽돌의 수를 세고 탐색을 종료한다.
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#define MAXH 16
#define MAXW 13
using namespace std;
int T, N, W, H, rst;
int map[MAXH][MAXW];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
void input() {
cin >> N >> W >> H;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cin >> map[i][j];
}
}
rst = (MAXH - 1) * (MAXW - 1);
}
int is_range(int x, int y) {
if (x >= 1 && x <= H && y >= 1 && y <= W) return true;
return false;
}
void cal_rst(int map[MAXH][MAXW]) {
int cnt = 0;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (map[i][j]) cnt++;
}
}
rst = min(rst, cnt);
}
void copy_map(int dst[MAXH][MAXW], int src[MAXH][MAXW]) {
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
dst[i][j] = src[i][j];
}
}
}
void bomb(int h, int w, int map[MAXH][MAXW]) {
queue <pair<int, int>> Q;
int nx, ny, val;
Q.push(make_pair(h, w));
while (!Q.empty()) {
int r = Q.front().first;
int c = Q.front().second;
val = map[r][c];
Q.pop();
map[r][c] = 0;
if (val == 1) continue;
for (int n = 1; n < val; n++) {
for (int i = 0; i < 4; i++) {
nx = r + dx[i] * n;
ny = c + dy[i] * n;
if (is_range(nx, ny) && map[nx][ny]) {
Q.push(make_pair(nx, ny));
}
}
}
}
}
void adjust(int map[MAXH][MAXW]) {
int temp[MAXH][MAXW] = { 0, };
for (int w = 1; w <= W; w++) {
int r = H;
for (int h = H; h >= 1; h--) {
if (map[h][w]) {
temp[r][w] = map[h][w];
r--;
}
}
}
copy_map(map, temp);
}
void dfs(int w, int depth, int map[MAXH][MAXW]) {
int flag = false;
int newmap[MAXH][MAXW] = { 0, };
copy_map(newmap, map);
for (int h = 1; h <= H; h++) {
if (map[h][w]) {
bomb(h, w, newmap);
adjust(newmap);
flag = true;
break;
}
}
if (!flag) {
cal_rst(newmap);
}
if (depth == N) {
cal_rst(newmap);
return;
}
for (int w = 1; w <= W; w++) {
dfs(w, depth + 1, newmap);
}
}
void solve() {
for (int i = 1; i <= W; i++) {
dfs(i, 1, map);
}
}
int main() {
cin >> T;
for (int tc = 1; tc <= T; tc++) {
input();
solve();
printf("#%d %d\n", tc, rst);
}
}
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#define MAXH 16
#define MAXW 13
using namespace std;
int T, N, W, H, rst;
int map[MAXH][MAXW];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
void input() {
cin >> N >> W >> H;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cin >> map[i][j];
}
}
rst = (MAXH - 1) * (MAXW - 1);
}
int is_range(int x, int y) {
if (x >= 1 && x <= H && y >= 1 && y <= W) return true;
return false;
}
void cal_rst() {
int cnt = 0;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (map[i][j]) cnt++;
}
}
rst = min(rst, cnt);
}
void copy_map(int dst[][MAXW], int src[][MAXW]) {
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
dst[i][j] = src[i][j];
}
}
}
void bomb(int h, int w) {
queue <pair<int, int>> Q;
int nx, ny, val;
Q.push(make_pair(h, w));
while (!Q.empty()) {
int r = Q.front().first;
int c = Q.front().second;
val = map[r][c];
Q.pop();
map[r][c] = 0;
if (val == 1) continue;
for (int n = 1; n < val; n++) {
for (int i = 0; i < 4; i++) {
nx = r + dx[i] * n;
ny = c + dy[i] * n;
if (is_range(nx, ny) && map[nx][ny]) {
Q.push(make_pair(nx, ny));
}
}
}
}
}
void adjust() {
int temp[MAXH][MAXW];
for (int w = 1; w <= W; w++) {
int r = H;
for (int h = H; h >= 1; h--) {
if (map[h][w]) {
temp[r][w] = map[h][w];
r--;
}
}
}
copy_map(map, temp);
}
void dfs(int w, int depth) {
int flag = false;
int c_map[MAXH][MAXW];
copy_map(c_map, map); // save
for (int h = 1; h <= H; h++) {
if (map[h][w]) {
bomb(h, w);
adjust();
flag = true;
break;
}
}
if (!flag) {
cal_rst();
}
if (depth == N) {
cal_rst();
copy_map(map, c_map); // restore
return;
}
for (int w = 1; w <= W; w++) {
dfs(w, depth + 1);
}
copy_map(map, c_map); // restore
}
void solve() {
for (int i = 1; i <= W; i++) {
dfs(i, 1);
}
}
int main() {
cin >> T;
for (int tc = 1; tc <= T; tc++) {
input();
solve();
printf("#%d %d\n", tc, rst);
}
}