글 읽기 - 반례 해결방법을 모르겠습니다....

culture1123 5년 전 0

각 방향으로는 잘 작동하는지는 확인하였습니다.

근데 dfs에서 이상해지는거 같은데 어디서 해결방법을 찾아야 할지 모르겠습니다 도와주세요

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int n;
int map[21][21];
int temp[21][21];
int ans = 0;
void mapc()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			temp[i][j] = map[i][j];
}
void mapr()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			map[i][j] = temp[i][j];
}
void dfs(int cnt)
{
	if (cnt == 5)
	{
		//show();
	//	cout << endl;
		int a = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (a < map[i][j])
				{
					a = map[i][j];
				}
			}
		}
		ans = max(ans, a);
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		//우
		mapc();
		if (i == 0)
		{
			
			deque<int> q;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (map[i][j] > 0)
					{
						q.push_back(map[i][j]);
						map[i][j] = 0;
					}
				}
			//	show();
			//	cout << endl;
			//	cout << q.size() << endl;
			//	cout << "go1" << endl;
			//	for (int a = 0; a < q.size(); a++)
			//	{
			//		cout << "qsize";
			//		cout << q[i];
			//	}
				int r = i;
				int c = n - 1;
				while (!q.empty())
				{
			//		show();
			//		cout << endl;
			//		cout << "go" << endl;
					int x = q.back();
					q.pop_back();

					if (map[r][c] == 0)
					{
						map[r][c] = x;
					}
					else if (map[r][c] == x)
					{
						map[r][c] = x * 2;
						c--;
					}
					else if (map[r][c] != x && map[r][c] != 0)
					{
						map[r][c - 1] = x;
						c--;
					}

				}
	//			cout << i << endl;
		//		show();
	//			cout << endl;
			}
		//	show();
			dfs(cnt + 1);
			mapr();
		}
	
		
		
		//위
	
		if (i == 1)
		{
			
			deque<int> q;
			for (int i = 0; i < n; i++)
			{
				for (int j = n-1; j >=0; j--)
				{
					if (map[j][i] > 0)
					{
						q.push_back(map[j][i]);
						map[j][i] = 0;
					}
				}
				int r = 0;
				int c = i;
				while (!q.empty())
				{
					//show();
					cout << endl;
					int x = q.back();
					q.pop_back();
					if (map[r][c] == 0)
					{
						map[r][c] = x;
					}
					else if (map[r][c] == x)
					{
						map[r][c] = x * 2;
						r++;
					}
					else if (map[r][c] != x && map[r][c] != 0)
					{
						map[r + 1][c] = x;
						r++;
					}
				}
				//show();
				cout << endl;
				
			}
			dfs(cnt + 1);
			mapr();

		}

		
		//좌
	
		if (i == 2)
		{
			deque<int> q;
			for (int i = 0; i < n; i++)
			{
				for (int j = n - 1; j >= 0; j--)
				{
					if (map[i][j] > 0)
					{
						q.push_back(map[i][j]);
						map[i][j] = 0;
					}
				}
				int r = i;
				int c = 0;
				while (!q.empty())
				{
					cout << endl;
				//	show();
					int x = q.back();
					q.pop_back();
					if (map[r][c] == 0)
					{
						map[r][c] = x;
					}
					else if (map[r][c] == x)
					{
						map[r][c] = x * 2;
						c++;
					}
					else if (map[r][c] != 0 && map[r][c] != x)
					{
						map[r][c + 1] = x;
						c++;
					}
				}
	//			cout << i << endl;
	//			show();
	//			cout << endl;
			}
			dfs(cnt + 1);
			mapr();
		}

		//하

		if (i == 3)
		{
	
			deque<int> q;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (map[j][i] > 0)
					{
						q.push_back(map[j][i]);
						map[j][i] = 0;
					}
				}
				int r = n-1;
				int c = i;
				while (!q.empty())
				{
				//	cout << endl;
					//show();
					int x = q.back();
					q.pop_back();
					if (map[r][c] == 0)
					{
						map[r][c] = x;

					}
					else if (map[r][c] == x)
					{
						map[r][c] = x * 2;
						r--;
					}
					else if (map[r][c] != 0 && map[r][c] != x)
					{
						map[r-1][c] = x;
						r--;
					}
					
				}
	//			cout << i << endl;
	//			show();
	//			cout << endl;
			}
			dfs(cnt + 1);
			mapr();

		}


	}
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
		}
	}
//	show();
	dfs(0);
	cout << ans << endl;
	return 0;
}

so6275 5년 전 0

dfs에 4방향 체크하는 for문에 i랑

map전체를 체크하는 for문에 i랑 안겹치나요??

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

문제

문제

출처

ICPC

반례 해결방법을 모르겠습니다....

culture1123 5년 전 0

so6275 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말