백준 17135 : 캐슬 디펜스 C++

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

후기

1. 무난하게 풀릴줄 알았는데 테케에 많이 걸려서 고생 무쟈게 한 문제

2. 거리가 똑같은게 여러개면 가장 왼쪽거 죽여야되는거를 적용안해서 계속 틀려서 너무 빡쳤었다

 

풀이

1. 조합으로 궁수 위치 설정

2. 나는 게임 끝나는거를 어차피 n이 15이하니까 그냥 n번만큼 루프 돌게 했다

3. 각 루프마다 죽일 적 정하고, 죽이고, 적들 한칸씩 내려오고 이 순서대로! 심플!

 

 

#include<iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, m, d;
int map[20][20];
int map_backup[20][20];
int check[20][20] = { 0, };
int archer[20] = { 0, };
int answer = 0;
int total_kill = 0;


void find_shortest(int index)
{
	int min = 987654421;
	int new_r = 100;//상관없는 이상한곳
	int new_c = 100;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 1)//위치에 적이 있구
			{
				if ((n-i + abs(j - index)) <= d)//범위 안이고!
				{
					if ((n - i + abs(j - index)) <= min)//최단 거리면!
					{
						if ((n - i + abs(j - index)) < min)
						{
							new_r = i;
							new_c = j;
							min = (n - i + abs(j - index));
							continue;
						}
						if (new_c > j)//만약 거리가 똑같으면 가장 왼쪽꺼를 죽여야함!!
						{
							new_r = i;
							new_c = j;
							min = (n - i + abs(j - index));
						}
					}
				}
			}
		}
	}
	check[new_r][new_c]++;
}

int kill()//궁수들이 죽인거!
{
	int cnt = 0;
	for (int i = 0; i < m; i++)
	{
		if (archer[i] == 1)
		{
			find_shortest(i);
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (check[i][j] >0)
			{
				map[i][j] = 0;
				check[i][j] = 0;
				cnt++;
			}
		}
	return cnt;
}


void start()
{
	total_kill = 0;
	int cnt = 0;
	while (true)
	{
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				check[i][j] = 0;

		total_kill += kill();//이번턴에 죽인거 점수에 더하기


		for (int i = n-1; i >0; i--)//적 한칸씩 내리기
		{
			for (int j = 0; j < m; j++)
			{
				map[i][j] = map[i - 1][j];
			}
		}
		for (int j = 0; j < m; j++)
		{
			map[0][j] = 0;
		}

		cnt++;
		if (cnt == n)
		{
			return;
		}
	}
}

void play_game(int index, int cnt)
{
	if (cnt == 3)//궁수 위치 정했으요
	{
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				map[i][j] = map_backup[i][j];
			}

		start();
		answer = max(answer, total_kill);
		return;
	}
	for (int i = index; i < m; i++)
	{
		if (archer[i] == 0)
		{
			archer[i] = 1;
			play_game(i, cnt + 1);
			archer[i] = 0;
		}
	}
}

int main()
{
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			map_backup[i][j] = map[i][j];
		}

	play_game(0,0);

	cout << answer << endl;
	return 0;
}