글 읽기 - 14%쯤에서 틀립니다. 진짜 이유를 못찾겠어요ㅜ

pentiumone 5년 전 0

dfs로 구현했고

for문 으로 0-오른쪽, 1-왼쪽, 2-아래쪽, 3-위쪽 으로 움직이게 구현했습니다.

구현할 때 예를들어 오른쪽이면 가장 오른쪽부터 시작해서, 만약 자기보다 오른쪽이 비어있으면 오른쪽으로 옮겨 놓고 그다음에 자신의 왼쪽에 있는 것을 찾아서 값이 같으면 합쳐주고 다르면 옆자리에 위치시킵니다.

게시판에 있는 TC까지 다 맞는데, 틀리게 나오네요 이유를 못찾겠습니다. 반례좀 알려주세요ㅠㅠ

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int n;
int ans = 0;

int prints(vector<vector<int>>&map) //최대값 출력부분
{
	int max = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] > max)
				max = map[i][j];
		}
	}
	return max;
}
void find(int count, vector<vector<int>>&maps)
{
	vector<vector<int>>temp = maps;
	if (count >= 5) //count==5해도 안됩니다ㅜㅜ
	{
		int tempmax = prints(temp);
		if (ans < tempmax)
			ans = tempmax;
		return;
	}
	for (int i = 0; i < 4; i++)//0-동,1-서,2-남,3-북
	{
		if (i == 0)//동쪽이동
		{
			for (int j = 1; j <= n;j++)
			{
				for (int k = n; k >= 1; k--)
				{
					int number = temp[j][k];
					if (number == 0)//숫자가 없으면 넘어간다.
						continue;
					int move = 1;
					if (k != n)//오른쪽 끝일 때는 할 필요 없음
					{
						while (1)//오른쪽에 빈칸이 있다면 움직인다.
						{
							if (k + move > n)
								break;
							if (temp[j][k + move] != 0)
								break;
							move++;
						}
						if (k + move > n)//오른쪽 끝이 비어 있을 때
						{
							temp[j][n] = temp[j][k];
							temp[j][k] = 0;
							k = n;
						}
						else if (temp[j][k + move] != 0) //끝이 아닐 때
						{
							if (move != 1)//move가 1이면 바로 옆이 있는거니까 스킵
							{
								temp[j][k + move-1] = temp[j][k];
								temp[j][k] = 0;
								k = k + move-1;
							}
						}
					}
					int tem = 1;
					while (1) //해당위치에 숫자가 있었을 때 왼쪽에 수가 있는지 찾는다.
					{
						if (k - tem < 1) //수가 없는 경우
							break;
						if (temp[j][k - tem] != 0) //수 를 발견
							break;
						tem++;
					}
					if (k - tem < 1) //수가 없으면 종료
						continue;
					if (temp[j][k - tem] == number) //숫자가 같을 때
					{
						temp[j][k] = number * 2;
						temp[j][k - tem] = 0;
					}
					else//숫자가 다를 때
					{
						if (temp[j][k - 1] != temp[j][k - tem])//바로옆에있는게 아닐 때만 움직여 줌
						{
							temp[j][k - 1] = temp[j][k - tem];
							temp[j][k - tem] = 0;
						}
					}
				}
			}
		}
		else if (i == 1) //서쪽 이동
		{
			for (int j = 1; j <= n; j++)
			{
				for (int k = 1; k <= n; k++)
				{
					int number = temp[j][k];
					if (number == 0)//숫자가 없으면 넘어간다.
						continue;
					int move = 1;
					if (k != 1)//왼쪽 끝일 때는 할 필요 없음
					{
						while (1)//왼쪽에 빈칸이 있다면 움직인다.
						{
							if (k - move < 1)
								break;
							if (temp[j][k - move] != 0)
								break;
							move++;
						}
						if (k - move < 1)//왼쪽 끝이 비어 있을 때
						{
							temp[j][1] = temp[j][k];
							temp[j][k] = 0;
							k = 1;
						}
						else if (temp[j][k - move] != 0) //끝이 아닐 때
						{
							if (move != 1)//move가 1이면 바로 옆이 있는거니까 스킵
							{
								temp[j][k - move+1] = temp[j][k];
								temp[j][k] = 0;
								k = k - move + 1;
							}
						}
					}
					int tem = 1;
					while (1) //해당위치에 숫자가 있었을 때 오른쪽에 수가 있는지 찾는다.
					{
						if (k + tem > n) //수가 없는 경우
							break;
						if (temp[j][k + tem] != 0) //수 를 발견
							break;
						tem++;
					}
					if (k + tem > n) //수가 없으면 종료
						continue;
					if (temp[j][k + tem] == number) //숫자가 같을 때
					{
						temp[j][k] = number * 2;
						temp[j][k + tem] = 0;
					}
					else//숫자가 다를 때
					{
						if (temp[j][k + 1] != temp[j][k + tem])//바로옆에있는게 아닐 때만 움직여 줌
						{
							temp[j][k + 1] = temp[j][k + tem];
							temp[j][k + tem] = 0;
						}
					}
				}
			}
		}
		else if (i == 2) //남쪽이동
		{
			for (int j = 1; j <= n; j++)
			{
				for (int k = n; k >= 1; k--)
				{
					int number = temp[k][j];
					if (number == 0)//숫자가 없으면 넘어간다.
						continue;
					int move = 1;
					if (k != n)//아래쪽 끝일 때는 할 필요 없음
					{
						while (1)//아래쪽에 빈칸이 있다면 움직인다.
						{
							if (k + move > n)
								break;
							if (temp[k+move][j] != 0)
								break;
							move++;
						}
						if (k + move > n)//아래쪽 끝이 비어 있을 때
						{
							temp[n][j] = temp[k][j];
							temp[k][j] = 0;
							k = n;
						}
						else if (temp[k+move][j] != 0) //끝이 아닐 때
						{
							if (move != 1)//move가 1이면 바로 옆이 있는거니까 스킵
							{
								temp[k+move-1][j] = temp[k][j];
								temp[k][j] = 0;
								k = k + move - 1;
							}
						}
					}
					int tem = 1;
					while (1) //해당위치에 숫자가 있었을 때 위쪽에 수가 있는지 찾는다.
					{
						if (k - tem < 1) //수가 없는 경우
							break;
						if (temp[k - tem][j] != 0) //수 를 발견
							break;
						tem++;
					}
					if (k - tem < 1) //수가 없으면 종료
						continue;
					if (temp[k-tem][j] == number) //숫자가 같을 때
					{
						temp[k][j] = number * 2;
						temp[k-tem][j] = 0;
					}
					else//숫자가 다를 때
					{
						if (temp[k - 1][j] != temp[k - tem][j])//바로 위에 있는게 아닐 때만 움직여
						{
							temp[k - 1][j] = temp[k - tem][j];
							temp[k - tem][j] = 0;
						}
					}
				}
			}
		}
		else if (i == 3)//북쪽이동
		{
			for (int j = 1; j <= n; j++)
			{
				for (int k = 1; k <= n; k++)
				{
					int number = temp[k][j];
					if (number == 0)//숫자가 없으면 넘어간다.
						continue;
					int move = 1;
					if (k != 1)//위쪽 끝일 때는 할 필요 없음
					{
						while (1)//위쪽에 빈칸이 있다면 움직인다.
						{
							if (k - move < 1)
								break;
							if (temp[k-move][j] != 0)
								break;
							move++;
						}
						if (k - move < 1)//위쪽 끝이 비어 있을 때
						{
							temp[k][1] = temp[k][j];
							temp[k][j] = 0;
							k = 1;
						}
						else if (temp[k-move][j] != 0) //끝이 아닐 때
						{
							if (move != 1)//move가 1이면 바로 옆이 있는거니까 스킵
							{
								temp[k-move+1][j] = temp[k][j];
								temp[k][j] = 0;
								k = k - move + 1;
							}
						}
					}
					int tem = 1;
					while (1) //해당위치에 숫자가 있었을 때 아래쪽에 수가 있는지 찾는다.
					{
						if (k + tem > n) //수가 없는 경우
							break;
						if (temp[k+tem][j] != 0) //수 를 발견
							break;
						tem++;
					}
					if (k + tem > n) //수가 없으면 종료
						continue;
					if (temp[k+tem][j] == number) //숫자가 같을 때
					{
						temp[k][j] = number * 2;
						temp[k+tem][j] = 0;
					}
					else//숫자가 다를 때
					{
						if (temp[k+1][j] != temp[k+tem][j])//바로옆에있는게 아닐 때만 움직여 줌
						{
							temp[k+1][j] = temp[k+tem][j];
							temp[k+tem][j] = 0;
						}
					}
				}
			}
		}
		find(count + 1, temp);
		temp = maps;
	}
}
int main()
{
	scanf("%d", &n);
	vector<vector<int>>map = vector<vector<int>>(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int temp;
			scanf("%d", &temp);
			map[i][j] = temp;
		}
	}
	find(0, map);
	printf("%d\n", ans);
	return 0;
}

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

문제

문제

출처

ICPC

14%쯤에서 틀립니다. 진짜 이유를 못찾겠어요ㅜ

pentiumone 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말