글 읽기 - 모든테스트케이스 전부 맞는데 어디가 틀린지 알려주실 수 있으신가요 ㅠㅠ

gktmddlr 3년 전 0

나와있는 모든케이스 정답이 나오는데 제출하면 게속 틀렸다고만하네요 ㅠㅠㅠ 혹시 알려주실 고수분 알려주세요 제발 ㅠㅠ

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

typedef struct Point {
	int x;
	int y;
};

int N;
int max = 0;

int map[21][21] = { { 0, } };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int dfs(int cnt);

int main() {

	int result;
	
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
/*
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d", map[i][j]);
		}
	}
	*/
	result = dfs(0);

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

	return 0;
}

int dfs(int cnt) {
	
	int SaveMap[21][21];
	int direction;
	int nx, ny;
	Point p;
	int flag;
	int result=0;
	int temp;
	vector<Point> v;

	//printf("cnt : %d\n", cnt);
	if (cnt == 5) {
		int search=0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (search < map[i][j]) search = map[i][j];
			}
		}
		return search;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			SaveMap[i][j] = map[i][j];
		}
	}

	direction = 0;
	for (int i = 1; i <= N; i++) {  //상
		for (int j = 1; j <= N; j++) {
			if (i - 1 == 0) { // 맨 윗줄
				continue;
			}
			else {
				if (map[i][j] == 0) continue;
				nx = i; ny = j;
				while (1) {
					flag = 0;
					nx = nx -1;
					ny = ny;
					if (nx == 0) break;
					if (map[nx][ny] == 0) {  // 위에가 비어있을때
						map[nx][ny] = map[nx + 1][ny];
						map[nx + 1][ny] = 0;
					}
					else if (map[nx][ny] == map[nx + 1][ny]) {  // 위에 같은 수가 있을때
						for (int k = 0; k < v.size(); k++) {
							if (nx == v[k].x && ny == v[k].y) {
								flag = 1;
							}
						}
						if (flag == 0) {
							map[nx][ny] = map[nx][ny] * 2;
							map[nx + 1][ny] = 0;
							p.x = nx; p.y = ny;
							v.push_back(p);
							break;
						}
						else {
							break;
						}
					}
				}
			}
		}
	}

	v.clear();
	/*
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	*/
	temp = dfs(cnt + 1);
	if (temp > result) result = temp;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j] = SaveMap[i][j];
		}
	}

	direction = 1;
	for (int i = N; i >=1; i--) {  //하
		for (int j = 1; j <= N; j++) {
			if (i + 1 > N) { // 맨 아랫줄
				continue;
			}
			else {
				if (map[i][j] == 0) continue;
				nx = i; ny = j;
				while (1) {
					flag = 0;
					nx = nx + 1;
					ny = ny;
					if (nx == N + 1) break;
					if (map[nx][ny] == 0) {  // 아래가 비어있을때
						map[nx][ny] = map[nx - 1][ny];
						map[nx - 1][ny] = 0;
					}
					else if (map[nx][ny] == map[nx - 1][ny]) {  // 위에 같은 수가 있을때
						for (int k = 0; k < v.size(); k++) {
							if (nx == v[k].x && ny == v[k].y) {
								flag = 1;
							}
						}
						if (flag == 0) {
							map[nx][ny] = map[nx][ny] * 2;
							map[nx - 1][ny] = 0;
							p.x = nx; p.y = ny;
							v.push_back(p);
							break;
						}
						else {
							break;
						}
					}
				}
			}
		}
	}

	v.clear();

	temp = dfs(cnt + 1);
	if (temp > result) result = temp;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j] = SaveMap[i][j];
		}
	}
	
	direction = 2;
	for (int i = 1; i <= N; i++) {  //좌
		for (int j = 1; j <= N; j++) {
			if (j - 1 == 0) { // 맨 왼쪽 줄
				continue;
			}
			else {
				if (map[i][j] == 0) continue;
				nx = i; ny = j;
				while (1) {
					flag = 0;
					nx = nx;
					ny = ny - 1;
					if (ny == 0) break;
					if (map[nx][ny] == 0) {  // 아래가 비어있을때
						map[nx][ny] = map[nx][ny + 1];
						map[nx][ny + 1] = 0;
					}
					else if (map[nx][ny] == map[nx][ny + 1]) {  // 위에 같은 수가 있을때
						for (int k = 0; k < v.size(); k++) {
							if (nx == v[k].x && ny == v[k].y) {
								flag = 1;
							}
						}
						if (flag == 0) {
							map[nx][ny] = map[nx][ny] * 2;
							map[nx][ny+1] = 0;
							p.x = nx; p.y = ny;
							v.push_back(p);
							break;
						}
						else {
							break;
						}
					}
				}
			}
		}
	}

	v.clear();

	temp = dfs(cnt + 1);
	if (temp > result) result = temp;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j] = SaveMap[i][j];
		}
	}

	direction = 3;
	for (int i = 1; i <= N; i++) {  //하
		for (int j = N; j >= 1; j--) {
			if (j + 1 > N) { // 맨 아랫줄
				continue;
			}
			else {
				if (map[i][j] == 0) continue;
				nx = i; ny = j;
				while (1) {
					flag = 0;
					nx = nx;
					ny = ny + 1;
					if (ny == N + 1) break;
					if (map[nx][ny] == 0) {  // 아래가 비어있을때
						map[nx][ny] = map[nx][ny - 1];
						map[nx][ny - 1] = 0;
					}
					else if (map[nx][ny] == map[nx][ny - 1]) {  // 위에 같은 수가 있을때
						for (int k = 0; k < v.size(); k++) {
							if (nx == v[k].x && ny == v[k].y) {
								flag = 1;
							}
						}
						if (flag == 0) {
							map[nx][ny] = map[nx][ny] * 2;
							map[nx][ny - 1] = 0;
							p.x = nx; p.y = ny;
							v.push_back(p);
							break;
						}
						else {
							break;
						}
					}
				}
			}
		}
	}

	v.clear();

	temp = dfs(cnt + 1);
	if (temp > result) result = temp;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j] = SaveMap[i][j];
		}
	}

	return result;
}

jh05013 3년 전 0

"나와있는 모든케이스 정답이 나오는데"

과연 그럴까요?

https://www.acmicpc.net/board/... 에 있는 세 번째 케이스에서 64가 나와야 되는데 128이 나옵니다.
https://www.acmicpc.net/board/... 에 위와 똑같은 케이스가 들어있습니다.
https://www.acmicpc.net/board/... 에도 위와 똑같은 케이스가 들어있습니다.

jh05013 3년 전 3

랜덤 반례 프로그램을 만든 기념으로 랜덤 반례를 드립니다.

5
2 8 32 0 0
32 8 8 0 0
16 4 16 4 8
0 2 4 0 4
0 8 2 32 0
Correct: 64
WRONG: 128

4
8 2 2 8
4 2 8 64
0 64 4 8
0 0 16 2
Correct: 64
WRONG: 128

5
8 0 0 32 16
4 64 4 2 16
0 2 128 0 0
2 8 2 4 2
64 0 32 8 2
Correct: 128
WRONG: 256

5
0 4 2 16 16
2 0 0 0 2
8 0 0 0 0
8 4 8 2 8
4 0 0 4 16
Correct: 32
WRONG: 64

5
2 4 2 0 8
16 8 4 4 2
16 8 8 32 2
8 0 4 2 16
0 0 16 8 32
Correct: 64
WRONG: 128

4
4 4 2 2
4 4 32 0
4 8 4 2
2 0 2 4
Correct: 32
WRONG: 64

5
0 8 4 0 16
2 4 8 2 2
4 4 4 0 2
2 2 8 2 2
0 0 4 32 0
Correct: 32
WRONG: 64

4
0 32 32 0
8 2 4 4
32 4 0 4
4 2 16 4
Correct: 64
WRONG: 128

5
2 32 8 8 2
0 0 8 4 32
2 16 2 64 0
0 8 4 8 4
0 8 0 16 4
Correct: 64
WRONG: 128

5
2 4 2 4 4
4 2 8 2 8
8 16 0 2 4
2 0 2 0 8
16 2 0 8 4
Correct: 32
WRONG: 64

4
32 2 64 8
4 2 4 32
2 32 8 0
8 8 32 2
Correct: 64
WRONG: 128

4
8 32 8 2
2 2 2 4
0 8 2 4
8 8 2 8
Correct: 32
WRONG: 64

5
8 4 16 2 2
2 2 2 8 16
0 2 0 8 2
2 2 8 8 16
4 4 2 2 64
Correct: 64
WRONG: 128

khj3753 3년 전 0

@jh05013

랜덤 반례 프로그램 덕분에 해결하고 갑니다 감사합니다

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

문제

문제

출처

ICPC

모든테스트케이스 전부 맞는데 어디가 틀린지 알려주실 수 있으신가요 ㅠㅠ

gktmddlr 3년 전 0

jh05013 3년 전 0

jh05013 3년 전 3

khj3753 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말