글 읽기 - 반례좀 찾아주세요.

hotgake 4년 전 0

질문 글들에서 제시해준 반례들도 통과하고, 예제들도 통과하고... 어떤 반례가 있길래 계속 틀리는건지 알고싶습니다.

#include <stdio.h>
#include <string.h>

int N, M, D;
int answer;
int archers[3];
int map[17][17];
int temp[17][17];
int num_enermies;

void make_combination(const int num_archers, const int start);
void calculate(void);
int kill_enermy(const int pos);
int can_move(const int R, const int C);
int move_enermy(void);

int main(void) {
	scanf("%d %d %d", &N, &M, &D);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) ++num_enermies;
		}
	}

	make_combination(0, 1);
	printf("%d\n", answer);
	return 0;
}

void make_combination(const int num_archers, const int start) {
	if (num_archers == 3) {
		calculate();
		return;
	}

	for (int i = start; i <= N; ++i) {
		archers[num_archers] = i;
		make_combination(num_archers + 1, i + 1);
	}
}

void calculate(void) {
	int ret = 0;
	int enermies = num_enermies;

	memcpy(temp, map, sizeof(map));
	while (enermies > 0) {
		for (int i = 0; i < 3; ++i) {
			int dead = kill_enermy(archers[i]);
			ret += dead;
			enermies -= dead; 
		}
		enermies -= move_enermy();
	}

	if (answer < ret)
		answer = ret;
}

int kill_enermy(const int pos) {
	int R, C;
	int mid_R;

	for (int i = 1; i <= D; ++i) {
		int difR = -1;
		int difC = 1;
		mid_R = N - i + 1;

		R = N;
		C = pos - i + 1;
		while (R <= N) {
			if (can_move(R, C)) {
				if (temp[R][C] == 1) {
					temp[R][C] = -1;
					return 1;
				}
				else if (temp[R][C] == -1)
					return 0;
			}

			if (R == mid_R)
				difR = 1;

			R += difR;
			C += difC;
		}
	}
	return 0;
}

int can_move(const int R, const int C) {
	if (R <= 0 || R > N) return 0;
	if (C <= 0 || C > M) return 0;
	return 1;
}

int move_enermy(void) {
	int ret = 0;

	for (int i = 1; i <= M; ++i)
		if (temp[N][i] == 1)
			++ret;

	for (int i = N; i > 0; --i)
		for (int j = 1; j <= M; ++j)
			temp[i][j] = (temp[i-1][j] == -1) ? 0 : temp[i-1][j];

	return ret;
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요.

hotgake 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말