글 읽기 - 반례좀 찾아주시면 감사하겠습니다

fox12395 4년 전 0

질문창에 있는 모든 테스트 케이스는 확인해봤는데 다 맞았습니다.

제출을 하면 바로 틀렸습니다가 나오는데 어느 부분에서 잘못된 걸까요...

소스의 경우 dfs를 통하여 만들 수 있는 모든 방향 조합을 만든후 game을 시작하게 구현하였습니다..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N;
int MAP[21][21];
int COPY[21][21];
int arrow[4] = { 5,5,5,5 }; // 상 우 하 좌
int ans = 0;
void print(vector <int> order) {
	printf("------%d %d %d %d %d---------\n", order[0],order[1],order[2],order[3],order[4]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%d ", COPY[i][j]);
		printf("\n");
	}
}
void upSide() {
	int visit[21][21];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//블록이 있다면 위로 올린다
			if (COPY[i][j] != 0) {
				int idx = i;
				int block = COPY[i][j];
				int last = i;
				int check = 0;
				while (idx--) {
					//위에 있는 블록이 옮길 블록과 똑같고 이미 합쳐진 블록이 아니라면 블록을 합친다
					if (COPY[idx][j] == block && visit[idx][j] != 1) {
						COPY[idx][j] += block;
						visit[idx][j] = 1;
						COPY[i][j] = 0;
						check = 1;
						break;
					}//위에 있는 블록이 0인 경우
					else if (COPY[idx][j] == 0) {
						last = idx;
					}//위에 있는 블록이 현재 블록과 값이 다른 경우
					else
						break;
				}
				if (check == 0) {
					COPY[i][j] = 0;
					COPY[last][j] = block;
				}
			}
		}
	}
}
void rightSide() {
	int visit[21][21];
	for (int i = 0; i < N; i++) {
		for (int j = N-2; j >= 0; j--) {
			//블록이 있다면 오른쪽으로 보낸다
			if (COPY[i][j] != 0) {
				int idx = j;
				int block = COPY[i][j];
				int last = j;
				int check = 0;
				while (idx++ != N-1) {
					//오른쪽에 있는 블록이 옮길 블록과 똑같고 이미 합쳐진 블록이 아니라면 블록을 합친다
					if (COPY[i][idx] == block && visit[i][idx] != 1) {
						COPY[i][idx] += block;
						visit[i][idx] = 1;
						COPY[i][j] = 0;
						check = 1;
						break;
					}//오른쪽에 있는 블록이 0인 경우
					else if (COPY[i][idx] == 0) {
						last = idx;
					}//오른쪽에 있는 블록이 현재 블록과 값이 다른 경우
					else
						break;
				}
				if (check == 0) {
					COPY[i][j] = 0;
					COPY[i][last] = block;
				}
			}
		}
	}
}
void downSide() {
	int visit[21][21];
	for (int i = N-2; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			//블록이 있다면 아래로 내린다
			if (COPY[i][j] != 0) {
				int idx = i;
				int block = COPY[i][j];
				int last = i;
				int check = 0;
				while (idx++ != N-1) {
					//아래에 있는 블록이 옮길 블록과 똑같고 이미 합쳐진 블록이 아니라면 블록을 합친다
					if (COPY[idx][j] == block && visit[idx][j] != 1) {
						COPY[idx][j] += block;
						visit[idx][j] = 1;
						COPY[i][j] = 0;
						check = 1;
						break;
					}//위에 있는 블록이 0인 경우
					else if (COPY[idx][j] == 0) {
						last = idx;
					}//위에 있는 블록이 현재 블록과 값이 다른 경우
					else
						break;
				}
				if (check == 0) {
					COPY[i][j] = 0;
					COPY[last][j] = block;
				}
			}
		}
	}
}
void leftSide() {
	int visit[21][21];
	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N; j++) {
			//블록이 있다면 왼쪽으로 보낸다
			if (COPY[i][j] != 0) {
				int idx = j;
				int block = COPY[i][j];
				int last = j;
				int check = 0;
				while (idx--) {
					//오른쪽에 있는 블록이 옮길 블록과 똑같고 이미 합쳐진 블록이 아니라면 블록을 합친다
					if (COPY[i][idx] == block && visit[i][idx] != 1) {
						COPY[i][idx] += block;
						visit[i][idx] = 1;
						COPY[i][j] = 0;
						check = 1;
						break;
					}//오른쪽에 있는 블록이 0인 경우
					else if (COPY[i][idx] == 0) {
						last = idx;
					}//오른쪽에 있는 블록이 현재 블록과 값이 다른 경우
					else
						break;
				}
				if (check == 0) {
					COPY[i][j] = 0;
					COPY[i][last] = block;
				}
			}
		}
	}
}
void playGame(vector <int> order) {
	//조건 1. 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다.
	//조건 2. 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

	//원본보드를 복사한다
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			COPY[i][j] = MAP[i][j];

	for (int i = 0; i < order.size(); i++) {
		int dir = order[i];

		if (dir == 0)
			upSide();
		else if (dir == 1)
			rightSide();
		else if (dir == 2)
			downSide();
		else if (dir == 3)
			leftSide();
		//print(order);
	}
	//print(order);

	//블록을 모두 옮긴 후 최대로 큰 블록값을 구한다.
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			ans = max(ans, COPY[i][j]);
}
void dfs(int idx, int depth, vector <int> order) {
	//최대 5번의 이동을 한 경우 가장 큰 블록의 값을 구한다
	if (depth > 5)
		return;

	playGame(order);
	for (int i = 0; i < 4; i++) {
		if (arrow[i] != 0) {
			arrow[i]--;
			order.push_back(i);
			dfs(i, depth + 1, order);
			order.pop_back();
			arrow[i]++;
		}
	}
}
int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			scanf("%d", &MAP[i][j]);

	// 상 하 좌 우 방향키의 5번 이동하는 모든 조합
	dfs(0, 0, {});

	printf("%d\n", ans);

	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주시면 감사하겠습니다

fox12395 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말