글 읽기 - 어느부분이 잘못된건지 여쭙고싶습니다.

apdh25 4년 전 0

28%에서 틀리다고 나오는데 제 생각에는 맞게 짠거같은데... 어느부분이 틀린건지 잘 모르겟습니다ㅠ..

한번 봐주시고 피드백주시면 감사드리겠습니다

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pair;

int N, D, M;
vector<vector<int>>board = vector < vector<int>>(16, vector<int>(16));
vector<Pair>hunters;
int answer = 0;

void init()
{
	cin >> N >> M >> D;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> board[i][j];
		}
	}
}

bool check_enermy(vector<vector<int>>board) {

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (board[i][j] == 1)
				return false;
		}
	}
	return true;
}

void do_hunt(vector<vector<int>>board)
{
	int hunted_cnt = 0;

	while (true)
	{
		Pair enermy[3] = { {0,0},{0,0},{0,0} };

		//적 다 제거되엇는지 확인
		if (check_enermy(board)) {
			answer = max(answer, hunted_cnt);
			break;
		}

		//각각의 헌터들이 적 사냥
		for (int k = 0; k < hunters.size(); k++)
		{
			int Near_D = 2e9;

			for (int i = 1; i <= N; i++)
			{
				for (int j = M; j >= 1; j--)
				{
					if (board[i][j])
					{
						int distance = abs(hunters[k].first - i) + abs(hunters[k].second - j);

						if (distance <= D) {
							if (distance <= Near_D)
							{
								enermy[k] = Pair(i, j);
								Near_D = distance;
							}
						}
					}
				}
			}
		}

		// 공격받은 적 제거
		for (int i = 0; i < 3; i++) {
			if (board[enermy[i].first][enermy[i].second]) {
				hunted_cnt++;
				board[enermy[i].first][enermy[i].second] = 0;
			}
		}

		// 적들 한칸씩 아래로 이동
		for (int i = N; i >= 1; i--)
		{
			for (int j = 1; j <= M; j++)
			{
				if (board[i][j])
				{
					if (i + 1 > N) {
						board[i][j] = 0;
					}
					else {
						board[i + 1][j] = board[i][j];
						board[i][j] = 0;
					}
				}
			}
		}
	}
}

void dfs(int idx, int cnt)
{
	if (cnt >= 3)
	{
		do_hunt(board);
		return;
	}

	for (int i = idx + 1; i <= M; i++)
	{
		hunters.push_back(Pair(N + 1, i));
		dfs(i, cnt + 1);
		hunters.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	init();
	dfs(0, 0);
	cout << answer << endl;
	return 0;
}

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

문제

문제

출처

ICPC

어느부분이 잘못된건지 여쭙고싶습니다.

apdh25 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말