글 읽기 - 예제 6번 질문있습니다.

piano9637 3년 전 0

궁수의 위치를 (6,0) (6,3) (6,4) 에 위치시키고 쏘면 13개를 궁수가 제거할수있는거 아닌가요?? 다른 태케는 맞는데 예제 6번만 14가 아닌 13이 나옵니다. 원인을 모르겠습니다 ㅠㅠ.

죽은 적은 y값을(first) -1로 처리하여 구분 했습니다.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
int N, M, D = 0;
int result = 0;
int arr[16][15] = { 0, };
int check[15] = { 0, };
pair<int, int> archer[3];
vector<pair<int, int>> enemy_temp;
vector<pair<int, int>> enemy;
void init(void)
{
	if(enemy_temp.size() != 0 )enemy_temp.clear();
	for (int i = 0; i < enemy.size(); i++)
	{
		enemy_temp.push_back(enemy[i]);
	}
	return;
}
void start_game(void)
{
	int cnt = 0;
	int cnt2 = 0;
	while (cnt2 != enemy.size())
	{
		queue<pair<int,int>> kill;
		for (int i = 0; i < 3; i++)
		{
			int maxnum = 987654321; int d = 0;
			int y = 987654321; int x = 987654321;
			for (int j = 0; j < enemy_temp.size(); j++)
			{
				if (enemy_temp[j].first == -1) continue;
				d = abs(archer[i].first - enemy_temp[j].first) + abs(archer[i].second - enemy_temp[j].second);
				if (d <= D) // 적과의 거리가 D이하
				{
					if (maxnum > d)
					{
						maxnum = d;
						y = enemy_temp[j].first; x = enemy_temp[j].second;
					}
					else if (maxnum == d) // 거리가 같은경우
					{
						if (x > archer[j].second) // 가장 왼쪽
						{
							y = archer[j].first;
							x = archer[j].second;
						}
					}
				}
			}
			if (maxnum != 987654321)
			{
				kill.push(make_pair(y, x));
			}
		}
		// 궁수들의 공격이 끝남
		// 적들제거후 
		while (kill.empty() == 0)
		{
			for (int j = 0; j < enemy_temp.size(); j++)
			{
				if (kill.front().first == enemy_temp[j].first && kill.front().second == enemy_temp[j].second)
				{
					enemy_temp[j].first = -1;
					cnt2++;
					cnt++;
					break;
				}
			}
			kill.pop();
		}
		// 적들은 아래로 한칸 이동
		for (int j = 0; j < enemy_temp.size(); j++)
		{
			if (enemy_temp[j].first != -1)
			{
				if (enemy_temp[j].first + 1 == N)
				{
					enemy_temp[j].first = -1;
					cnt2++;
				}
				else enemy_temp[j].first += 1;
			}
		}
	}
	result = max(result, cnt);
	return;
}
void archer_pos(int index, int cnt)
{
	if (cnt == 3) // 궁수의 위치가 모두 정해졌을때
	{
		// 게임 시작
		init();
		start_game();
		return;
	}
	else
	{
		for (int i = index; i < M; i++)
		{
			if (check[i] == 0)
			{
				check[i] = 1;
				archer[cnt] = make_pair(N,i);
				archer_pos(i + 1, cnt + 1);
				check[i] = 0;
			}
		}
	}
	return;
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1)
			{
				enemy.push_back(make_pair(i, j));
			}
		}
	}
	// 궁수의 위치 case
	for (int i = 0; i < M; i++)
	{
		if (check[i] == 0)
		{
			check[i] = 1;
			archer[0] = make_pair(N, i);
			archer_pos(i + 1, 1);
			check[i] = 0;
		}
	}
	cout << result;
}

kimyh0316 3년 전 0

0,3,4에 위치시키면 13이 맞습니다.

piano9637 3년 전 0

헉 그러면 멘탈을 가다듬어서 다른경우를 생각해 봐야되겠네요 ㅠㅠ 감사합니다

piano9637 3년 전 1

궁수의 타겟 적을 중복제거하여 저장하고 한칸으로 이동하다가 성을 만난 적들도 벡터에서 바로 제거 해주니 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제 6번 질문있습니다.

piano9637 3년 전 0

kimyh0316 3년 전 0

piano9637 3년 전 0

piano9637 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말