벽돌 깨기 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
struct MOVE { int x, y; };
MOVE mv[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
const int MAX = 16;
int map[MAX][MAX];
int n, w, h;
int answer = 0;

void DeleteMap(int m[MAX][MAX], int count, int ans) {
	if (count == n) {
		answer = max(answer, ans);
		return;
	}

	vector<int> top;
	bool left = false;
	for (int j = 0; j < w; j++) {
		bool flag = false;
		for (int i = 0; i < h; i++) {
			if (m[i][j] != 0) {
				top.push_back(i);
				flag = true;
				left = true;
				break;
			}
		}
		if (flag == false) {
			top.push_back(-1);
		}
	}
	if (left == false) answer = max(answer, ans);

	for (int i = 0; i < top.size(); i++) {
		if (top[i] == -1) continue;
		int tmp_ans = 0;

		int visited[MAX][MAX];
		memset(visited, -1, sizeof(visited));
		queue<pair<int, int>> q;
		q.push({ top[i],i });
		visited[top[i]][i] = 1;
		
		int tmp[MAX][MAX];
		for (int ii = 0; ii < h; ii++) {
			for (int jj = 0; jj < w; jj++) {
				tmp[ii][jj] = m[ii][jj];
			}
		}

		while(!q.empty()){
			int ii = q.front().first;
			int jj = q.front().second;
			int value = m[ii][jj]-1;
			if (tmp[ii][jj] != 0) tmp_ans++;
			tmp[ii][jj] = 0;
			q.pop();

			for (int k = 0; k < 4; k++) {
				int movei = ii;
				int movej = jj;
				for (int c = value; c > 0; c--) {
					movei += mv[k].x;
					movej += mv[k].y;

					if (!(movei >= 0 && movei < h && movej >= 0 && movej < w)) continue;
					if (visited[movei][movej] == 1) continue;

					visited[movei][movej] = 1;
					q.push({ movei,movej });
				}
			}
		}

		for (int j = 0; j < w; j++) {
			vector<int> v;
			for (int i = h-1; i >= 0; i--) {
				if (tmp[i][j] != 0) {
					v.push_back(tmp[i][j]);
				}
				tmp[i][j] = 0;
			}

			int id = h - 1;
			for (int i = 0; i < v.size(); i++) {
				tmp[id][j] = v[i];
				id--;
			}
		}

		DeleteMap(tmp, count + 1, ans + tmp_ans);
	}
}

int main(void) {
	int testcase;
	cin >> testcase;
	int index = 1;

	for (; testcase > 0; testcase--) {
		cin >> n >> w >> h;
		int count = 0;

		answer = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				if (map[i][j] != 0) count++;
			}
		}

		DeleteMap(map, 0, 0);

		cout << "#" << index << " " << count-answer << endl;
		index++;
	}
}