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

rudtn1406 4년 전 0

32% 정도에서 오답처리되는데 도저히 모르겠습니다 ㅠㅠ

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int ARR_MAX = 18;
typedef pair<int, int> P;
int map[ARR_MAX][ARR_MAX];
bool visited[ARR_MAX][ARR_MAX];
int archers[3];
vector<P> death;
int N, M, D, answer = 0;

int dx[3] = { 0, -1, 0 };
int dy[3] = { -1, 0, 1 };

void initVisited()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = false;
		}
	}
}

void copyMap(int(*a)[ARR_MAX], int(*b)[ARR_MAX])
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			a[i][j] = b[i][j];
}

bool isPlace(P p) { return (p.first >= 0 && p.first < N) && (p.second >= 0 && p.second < M); }

void BFS(int archer, int(*tempMap)[ARR_MAX])
{
	initVisited();
	queue<pair<int, int>> q;
	q.push(make_pair(N - 1, archer));
	for (int i = 1; i <= D; i++) {
		int Size = q.size();
		while (Size--) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			if (tempMap[x][y] == 1) {
				death.push_back(make_pair(x, y));
				return;
			}
			for (int d = 0; d < 3; d++) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				if (!isPlace(make_pair(nx, ny)) || visited[nx][ny]) continue;
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

int simulation()
{
	int tempMap[ARR_MAX][ARR_MAX];
	copyMap(tempMap, map);
	int deathEnemy = 0;

	for (int wave = 0; wave < N; wave++) {
		for (int idx = 0; idx < 3; idx++) {
			BFS(archers[idx], tempMap);
		}

		for (int idx = 0; idx < death.size(); idx++) {
			int x = death[idx].first;
			int y = death[idx].second;
			if (tempMap[x][y] == 1) {
				deathEnemy++;
				tempMap[x][y] = 0;
			}
		}
		death.clear();

		for (int i = N-1; i > wave; i--) {
			for (int j = 0; j < M; j++) {
				tempMap[i][j] = tempMap[i - 1][j];
			}
		}
		for (int i = 0; i < M; i++) {
			tempMap[wave][i] = 0;
		}
	}
	return deathEnemy;
}

void DFS(int idx, int depth)
{
	if (depth == 3) {
		answer = max(answer, simulation());
		return;
	}
	for (int i = idx; i < M; i++) {
		archers[depth] = i;
		DFS(i + 1, depth + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	DFS(0, 0);

	cout << answer;
	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요 ㅠㅠ

rudtn1406 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말