캐슬 디펜스 C++

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

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

using namespace std;
struct MOVE { int x, y; };
MOVE mv[4] = { {0,-1}, {-1,0}, {0,1} };
const int MAX = 17;
int n, m, d;
int map[MAX][MAX];
int answer = -1;
struct INFO { int x, y, count; };
void chooseSeat(vector<int> seat, int index, int count);
int sz = 0;

void cal(vector<int> seat) {
	int tmp_ans = 0;
	int tmp_map[MAX][MAX];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmp_map[i][j] = map[i][j];
		}
	}

	while (true) {
		vector<pair<int,int>> die;
		for (int i = 0; i < 3; i++) {
			int visited[MAX][MAX];
			memset(visited, -1, sizeof(visited));
			queue<INFO> q;
			q.push({ n,seat[i],0 });
			pair<int, int> tmp = { 20,20 };

			while (!q.empty()) {
				int ii = q.front().x;
				int jj = q.front().y;
				int c = q.front().count;
				q.pop();

				if (c > d) break;
				if (tmp_map[ii][jj] == 1 && (ii >=0 && ii <n && jj >=0 && jj <m)) {
					tmp = { ii,jj };
					break;
				}

				for (int k = 0; k < 3; k++) {
					int movei = ii + mv[k].x;
					int movej = jj + mv[k].y;

					if (!(movei >= 0 && movei <= n && movej >= 0 && movej < m)) continue;
					if (visited[movei][movej] == 1) continue;
					
					visited[movei][movej] = 1;
					q.push({ movei,movej,c+1 });
				}
			}

			if (tmp.first >= 0 && tmp.first < n && tmp.second >= 0 && tmp.second < m) {
				die.push_back(tmp);
			}
		}

		for (int k = 0; k < die.size(); k++) {
			if (tmp_map[die[k].first][die[k].second] == 1) tmp_ans++;
			tmp_map[die[k].first][die[k].second] = 0;
		}

		bool flag = false;
		for (int ii = n-2; ii >=0; ii--) {
			for (int jj = 0; jj < m; jj++) {
				if (tmp_map[ii][jj] == 1) flag = true;
				tmp_map[ii + 1][jj] = tmp_map[ii][jj];
			}
		}

		if (flag == false) break;
		for (int jj = 0; jj < m; jj++) {
			tmp_map[0][jj] = 0;
		}
	}

	answer = max(answer, tmp_ans);
}

void chooseSeat(vector<int> seat,int index) {
	for (int i = 0; i < m; i++) {
		for (int j = i + 1; j < m; j++) {
			for (int k = j + 1; k < m; k++) {
				cal({ i,j,k });
			}
		}
	}
}

int main(void) {
	cin >> n >> m >> d;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) sz++;
		}
	}

	chooseSeat({},0);
	cout << answer << endl;
}