글 읽기 - 반례를 알고 싶습니다ㅜ

rjsgml1028 5년 전 0

우선 질문 읽어주셔서 감사합니다.

다음과 같이 코드를 짜보고 생각할 수 있는 여러 테스트 케이스를 입력해봤는데

어떤 반례가 있어서 틀리는건지 찾지 못해 질문올립니다.

#include <iostream>
#define MAX 20
using namespace std;

struct BLOCK {
	int value;
	int is_merged;
};
int N;
BLOCK map[MAX][MAX];
int max_v;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void map_copy(BLOCK map[][MAX], BLOCK copy_map[][MAX]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
}

void shift_block(int x, int y, int d) {
	if (d == 0) {
		for (int i = y; i > 0; i--) {
			if (!map[x][i].value) {
				map[x][i].value = map[x][i - 1].value;
				map[x][i - 1].value = 0;
			}
		}
	}
	else if (d == 1) {
		for (int i = x; i > 0; i--) {
			if (!map[i][y].value) {
				map[i][y].value = map[i - 1][y].value;
				map[i - 1][y].value = 0;
			}
		}
	}
	else if (d == 2) {
		for (int i = y; i < N - 1; i++) {
			if (!map[x][i].value) {
				map[x][i].value = map[x][i + 1].value;
				map[x][i + 1].value = 0;
			}
		}
	}
	else {
		for (int i = x; i < N - 1; i++) {
			if (!map[i][y].value) {
				map[i][y].value = map[i + 1][y].value;
				map[i + 1][y].value = 0;
			}
		}
	}
}

void merge_block(BLOCK *b1, BLOCK *b2) {
	b1->value *= 2;
	b2->value = 0;

	b1->is_merged = 1;
}

void move_block(int d) {
	if (d == 0) {
		for (int i = N - 1; i > 0; i--) {
			for (int j = 0; j < N; j++) {
				if (map[j][i].value == map[j][i - 1].value && !map[j][i].is_merged) {
					merge_block(&map[j][i], &map[j][i - 1]);
					shift_block(j, i - 1, d);
				}
				else if (!map[j][i].value) {
					shift_block(j, i, d);
				}
			}
		}
	}
	else if (d == 1) {
		for (int i = N - 1; i > 0; i--) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].value == map[i - 1][j].value && !map[i][j].is_merged) {
					merge_block(&map[i][j], &map[i - 1][j]);
					shift_block(i - 1, j, d);
				}
				else if (!map[i][j].value) {
					shift_block(i, j, d);
				}
			}
		}
	}
	else if (d == 2) {
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j < N; j++) {
				if (map[j][i].value == map[j][i + 1].value && !map[j][i].is_merged) {
					merge_block(&map[j][i], &map[j][i + 1]);
					shift_block(j + 1, i, d);
				}
				else if (!map[j][i].value) {
					shift_block(j, i, d);
				}
			}
		}
	}
	else {
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].value == map[i + 1][j].value && !map[i][j].is_merged) {
					merge_block(&map[i][j], &map[i + 1][j]);
					shift_block(i, j + 1, d);
				}
				else if (!map[i][j].value) {
					shift_block(i, j, d);
				}
			}
		}
	}
}

int find_max() {
	int max = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (max < map[i][j].value) max = map[i][j].value;
		}
	}
	return max;
}

void dfs(int d, int cnt) {
	if (cnt == 5) {
		int max = find_max();

		if (max_v < max) max_v = max;

		return;
	}

	move_block(d);

	for (int i = 0; i < 4; i++) {
		BLOCK copy_map[MAX][MAX];
		map_copy(map, copy_map);

		dfs(i, cnt + 1);

		map_copy(copy_map, map);
	}
}

void input() {
	max_v = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j].value;
			map[i][j].is_merged = 0;
		}
	}
}

int main() {
	cin >> N;

	input();

	for (int i = 0; i < 4; i++) {
		BLOCK copy_map[MAX][MAX];
		map_copy(map, copy_map);

		dfs(i, 0);

		map_copy(copy_map, map);
	}

	cout << max_v;

	return 0;
}

djm03178 5년 전 0

질문을 올릴 때 위에 읽으라고 나오는 공지사항을 보면, 굵은 글씨로 "질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요." 라고 되어있습니다.

https://www.acmicpc.net/board/view/34909 에서 반례가 나옵니다.

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

문제

문제

출처

ICPC

반례를 알고 싶습니다ㅜ

rjsgml1028 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말