백준12100번 2048 (Easy)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

#pragma warning(disable : 4996)

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
int T, N;
int com[21][21];

//right down left up
int dy[4] = { 0,1,0,-1 }; // row
int dx[4] = { 1,0,-1,0 }; // col
void copy_arr(int dst[][21], int src[][21])
{
	for (int i = 0; i < 21; i++)
	{
		for (int j = 0; j < 21; j++)
			dst[i][j] = src[i][j];
	}
}
void init(int arr[][21])
{
	for (int i = 0; i < 21; i++)
		memset(arr[i], 0, sizeof(arr[i]));
}
void Move_up(int ptile[][21])
{
	for (int i = 0; i < N; i++) //col
	{
		int r = 0;
		int last_num_idx = 0;

		for (int j = 0; j < N - 1; j++) //row
		{
			if (ptile[j][i] > 0)
			{
				last_num_idx = j;
				if (ptile[j + 1][i] == ptile[j][i] && com[j][i] == 0 && com[j + 1][i] == 0) // check down
				{
					ptile[j][i] = ptile[j][i] * 2;
					ptile[j + 1][i] = 0;
					com[j][i] = 1;
				}
			}
			else if (ptile[j][i] == 0)
			{
				r = j;
				while (ptile[r][i] == 0 && r < N - 1)
					r++;
				if (r == N - 1)
				{
					ptile[r - 1][i] = ptile[r][i];
					ptile[r][i] = 0;
					break;
				}
				int k;
				for (k = 0; k < N - j - 1; k++)
				{
					if (r + k >= N)
					{
						ptile[j + k][i] = 0;
						continue;
					}
					ptile[j + k][i] = ptile[r + k][i];
				}
				ptile[j + k][i] = 0;
				j--;
				if (j >= 0 && ptile[j + 1][i] == ptile[j][i] && com[j][i] == 0 && com[j + 1][i] == 0) // check down
				{
					ptile[j][i] = ptile[j][i] * 2;
					ptile[j + 1][i] = 0;
					com[j][i] = 1;
				}
			}
		}

	}
}
void change_up_down(int ptile[][21])
{
	int n_tile[21][21];
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			n_tile[i][j] = ptile[N - i - 1][j];
	}
	copy_arr(ptile, n_tile);
}
void cr_to_t(int srctile[][21], int dsttile[][21]) //change row and col
{
	for (int i = 0; i < 21; i++)
	{
		for (int j = 0; j < 21; j++)
		{
			dsttile[j][i] = srctile[i][j];
		}
	}
}
void Move(char dir, int tile[][21], int tile_col_row[][21])
{
	if (dir == 'u')
		Move_up(tile);
	else if (dir == 'd') {
		change_up_down(tile);
		Move_up(tile);
		change_up_down(tile);
	}
	else if (dir == 'l')
	{
		Move_up(tile_col_row);
		cr_to_t(tile_col_row, tile);
	}
	else if (dir == 'r')
	{
		change_up_down(tile_col_row);
		Move_up(tile_col_row);
		change_up_down(tile_col_row);
		cr_to_t(tile_col_row, tile);
	}

}

int maxnum = 0;
void dfs(int tile[][21], int tile_col_row[][21], int nmax, int cnt)
{
	if (cnt > 5)
		return ;
	if (nmax > maxnum)
		maxnum = nmax;
	char dir[4] = { 'l', 'r', 'd', 'u' };
	for (int i = 0; i < 4; i++)
	{
		init(com);
		priority_queue<int> n_q;
		int ntile[21][21];
		int ntile_col_row[21][21];
		copy_arr(ntile, tile);
		cr_to_t(tile, ntile_col_row);
		Move(dir[i], ntile, ntile_col_row);
		for (int r = 0; r < N; r++)
		{
			for (int c=0; c<N; c++)
			{
				n_q.push(ntile[r][c]);
			}
		}
		dfs(ntile, ntile_col_row, n_q.top(), cnt + 1);
	}
}
int main()
{
	priority_queue <int> ini;
	int tile[21][21];
	int tile_col_row[21][21];
	init(com);
	init(tile);
	init(tile_col_row);
	N = 0;
	scanf("%d", &N);
	for (int j = 0; j < N; j++)
	{
		for (int k = 0; k < N; k++)
		{
			int n;
			scanf("%d", &n);
			ini.push(n);
			tile[j][k] = n;
			tile_col_row[k][j] = n;

		}
	}
	dfs(tile, tile_col_row, 0, 0);
	printf("%d", maxnum);
	int s = 0;
	return 0;

}