글 읽기 - [C++]정답이라 생각했는데 바로 틀렸습니다가 나오네요 반례가 있을까요 ?

sure97 4년 전 0

테스트케이스는 모두 맞게 나옵니다.

초기에 map값을 모두 -1로 설정하여 사용되지 않는 index는 모두 -1로 설정되어있습니다.

(index는 1~N,1~M을 사용하였습니다. map[0][j],map[i][0] 모두 -1로 설정)

그 후 범위 내의 입력을 map에 받고

search 함수를 통해 궁수가 위치할 수 있는 모든 경우의 수에 대해 게임을 진행하였습니다.

map값은 바꿔주지 않고 _map에 복사해서 사용하였습니다.

attack 함수는 궁수의 x좌표를 입력받으면 공격할 적의 좌표를 return합니다.

적이 없는 경우, -1,-1을 리턴합니다.

gameplay함수 안에서 한 라운드에 궁수들이 같은 적을 쏘는 경우도 제외하였고

move함수는 한 라운드가 끝날 때마다 _map의 값을 한칸씩 아래로 내렸습니다.

문제 조건 모두 맞게 구현한 듯 하고,

게시판 반례와 테스트케이스 모두 맞게 나오는데

제출하면 바로 틀렸습니다가 떠버립니다

어떤 반례가 있을까요 ?

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define n 18
using namespace std;

pair<int, int> attack(int x);
void gameset();
void move(int x);
void gameplay(int a, int b, int c);
void search(int k, int index);


int N, M, D, map[n][n], _map[n][n];
int arr[3], maxkill;

pair<int, int> attack(int x) {
	int range = 1;
	queue<pair<int, int>> q;
	q.push({ N ,x });
	while (range <= D) {
		int size = q.size();
		while (size > 0) {
			int i = q.front().first;
			int j = q.front().second;
			q.pop();
			if (_map[i][j] == -1) {
				size--;
				continue;
			}
			if (_map[i][j] == 1) {
				return { i,j };
			}

			if (j < x) {
				if (j > 0)
					q.push({ i,j - 1 });
			}
			else if (j == x) {
				q.push({ i - 1,j });
				q.push({ i,j - 1 });
				q.push({ i,j + 1 });
			}
			else {
				if (j < M)
					q.push({ i,j + 1 });
			}
			size--;
		}
		range++;
	}

	return { -1,-1 };
}

void gameset() {
	memcpy(_map, map, sizeof(map));
}

void move(int x) {
	for (int i = N; i > x; i--) {
		memcpy(_map[i + 1], _map[i], sizeof(_map[i]));
	}
}

void gameplay(int a,int b,int c) {
	gameset();
	int round = 0, x, y;
	int kill = 0;
	pair<int, int> p[3];
	while (round < N) {
		p[0] = attack(a);
		p[1] = attack(b);
		p[2] = attack(c);
		for (int i = 0; i < 3; i++) {
			x = p[i].first;
			y = p[i].second;
			if (x == -1 || y == -1 || _map[x][y] == 0)
				continue;
			else {
				kill++;
				_map[x][y] = 0;
			}
		}
		move(round);
		round++;
		if (maxkill < kill)
			maxkill = kill;
	}
	
}

void search(int k, int index) {
	if (k > M)
		return;
	if (index == 3) {
		gameplay(arr[0], arr[1], arr[2]);
	}
	else {
		arr[index] = k + 1;

		search(k + 1, index + 1);
		search(k + 1, index);
	}
	return;
}


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> D;
	memset(map, -1, sizeof(map));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}

	search(0, 0);
	cout << maxkill << endl;
}

sure97 4년 전 0

42번째 줄과 43번째 줄이 순서가 바뀌었었네요 ㅠ
수정해서 제출하니 맞았습니다 !

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