https://www.acmicpc.net/problem/12100
#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;
}
728x90
'코테 > 백준 문제풀이' 카테고리의 다른 글
백준 1697번 파이썬 (0) | 2023.01.01 |
---|---|
백준 21611 마법사 상어와 블리자드 (0) | 2022.04.29 |
백준 3055 탈출 (1) | 2021.08.24 |
백준 1987 알파벳 (0) | 2021.08.16 |
백준 1697 숨바꼭질 (1) | 2021.08.12 |