백준 - 캐슬 디펜스 [17135]

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;
int result = 0;
int map[15][15];
int map2[15][15];

void attack(int row, int col, int d, vector<int> s) {
	int temp_length = 100;
	int temp_num = 0;
	int flag2 = false;
	bool min = false;
	vector<pair<int, int>> list;

	for (int i = 0; i < (int)s.size(); i++) {
		vector<pair<int, int>> s_list;
		for (int j = 1; j <= d; j++) {
			for (int k = 0; k < col; k++) {
				if ((abs(s[i] - k) + j) <= d && map[row - j][k] == 1) {
					if (temp_length >= (abs(s[i] - k) + j)) {
						temp_length = (abs(s[i] - k) + j);
						temp_num = k;
						s_list.push_back(make_pair(temp_num, row - j));
						flag2 = true;
						if (temp_length == 1)
							min = true;
					}
				}
				if (min)
					break;
			}
			if (min)
				break;
			if (j == row)
				break;
		}

		if (flag2) {
			sort(s_list.begin(), s_list.end());
			for (int q = 0; q < (int)s_list.size(); q++)
				if ((abs(s_list[q].first - s[i]) + row - s_list[q].second) == temp_length)	{
					list.push_back(make_pair(s_list[q].second, s_list[q].first));
					break;
				}
			flag2 = false;
		}
		min = false;
		temp_length = 100;
		temp_num = 0;
	}
	for (int i = 0; i < (int)list.size(); i++) {
		if (map[list[i].first][list[i].second] == 1) {
			map[list[i].first][list[i].second] = 0;
			result++;
		}

	}

}

int main() {
	int row, col, d;
	vector<int> ind;
	int fin = 0;
	cin >> row >> col >> d;

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
			map2[i][j] = map[i][j];
		}
	}

	for (int i = 0; i < col - 3; i++)
		ind.push_back(0);
	ind.push_back(1);
	ind.push_back(1);
	ind.push_back(1);


	do {
		vector<int> s;
		for (int i = 0; i < col; i++)
			if (ind[i] == 1)
				s.push_back(i);

		for (int a = 0; a < row; a++) {
			attack(row, col, d, s);
			for (int i = row - 1; i >= 0; i--) {
				if (i == row - 1)
					continue;

				for (int j = 0; j < col; j++) {
					map[i + 1][j] = map[i][j];
				}
				if (i == 0) {
					for (int j = 0; j < col; j++)
						map[i][j] = 0;
				}
			}
		}
		if (result > fin)
			fin = result;
		result = 0;
		for (int i = 0; i < row; i++)
			for (int j = 0; j < col; j++)
				map[i][j] = map2[i][j];
	} while (next_permutation(ind.begin(), ind.end()));

	std::cout << fin;

	return 0;
}