[백준 17135] 캐슬디펜스

찢었다

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

17135번: 캐슬 디펜스

#include <cstdio>
#include <vector>
#include <set>
#include <cstdlib>
#include <cstring>
int N, M, D;
int board[15 + 2][15 + 2];
int tmp[15 + 2][15 + 2];
int ans;

std::vector<int> Arc;

void input()
{
	scanf("%d %d %d", &N, &M, &D);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}

void set_castle()
{
	for (int j = 0; j < M; j++) {
		board[N][j] = 2;
	}
}


bool chk_left(int row)
{
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < M; j++) {
			if (tmp[i][j] == 1) return true;
		}
	}
	return false;
}




int kill_enemy()
{
	memcpy(tmp, board, sizeof(board));
	
	int row = N;
	int cnt = 0;

	std::set<std::pair<int, int>> E;

	while (1) {
		// 격자에 적 남았는지 확인
		if (!chk_left(row)) return cnt;

		E.clear();
		// 궁수 별 가까운 적 구하기 
		for (int a : Arc) {
			int min = 0x7fffffff;
			int opt_row = -1;
			int opt_col = 0x7fffffff;
			bool killed = false;
			
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < M; j++) {
					if (tmp[i][j] == 1) {
						int dist = abs(row - i) + abs(a - j);
						if (dist > D) continue;
						if (min > dist ||
							(min == dist) && (opt_col > j)) {
							min = dist;
							opt_row = i;
							opt_col = j;
							killed = true;
						}
					}
				}
			}
			// 좌표 중복 안생기도록 set 사용 
			// 쓰레기값 안담기게 플래그 사용 
			if (killed == true) E.insert({ opt_row, opt_col });
		}

		// 적 죽이기 
		if (E.size() > 0) {
			for (auto iter = E.begin(); iter != E.end(); iter++) {
				tmp[iter->first][iter->second] = 0;
				cnt++;
			}
		}

		// 성 한 칸 올리기 
		row--;
		for (int j = 0; j <= M; j++) {
			tmp[row][j] = 2;
		}
	}
	memset(tmp, 0, sizeof(tmp));
}



void DFS(int n, int arc)	// 몇 번째 열에 궁수를 배치할 것인지 
{
	if (arc > 4) return;	// 궁수는 3명까지만 배치한다
	
	if (arc == 3) {
		int score = kill_enemy();
		if (ans < score) ans = score;
		return;
	}

	if (n == M) return;


	// 해당 칸에 궁수 배치 한다
	Arc.push_back(n);
	DFS(n + 1, arc + 1);
	Arc.pop_back();

	// 해당 칸에 궁수 배치 안한다
	DFS(n + 1, arc);
}


int main()
{
	input();
	set_castle();
	DFS(0, 0);
	printf("%d\n", ans);
	return 0;
}

와 한달 전에 접근도 못하던 문제 55분컷 함

진짜 너무 행복하다