반응형

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

 

12094번: 2048 (Hard)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

 

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21], ans = 0, real_ans=0;
int L_max[11];

void up(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i-1;

				while ((p - 1 >= 0) && (arr_[p][j] == 0)) {
					p--;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p + 1][j]);
					}
				}
			}
		}
	}
}


void down(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = n-2; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i + 1;

				while ((p + 1 <= n - 1) && (arr_[p][j] == 0)) {
					p++;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p - 1][j]);
					}
				}
			}
		}
	}
}


void Left(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = j - 1;

				while ((p - 1 >= 0) && (arr_[i][p] == 0)) {
					p--;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p+1]);
					}
				}
			}
		}
	}
}


void Right(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = n - 2; j >= 0; j--) {
			if (arr_[i][j] > 0) {
				int p = j + 1;

				while ((p + 1 <= n - 1) && (arr_[i][p] == 0)) {
					p++;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p-1]);
					}
				}

			}
		}
	}
}

void copyArray(int arr_[][21], int arr[][21]) {
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			arr_[i][j] = arr[i][j];
		}
	}
}

bool isdif(int arr_[][21], int arr[][21]){
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			if (arr_[i][j] != arr[i][j]) {
				return true;
			}
		}
	}
	return false;
}


void DFS(int arr[][21], int L) {
	int arr_[21][21];
	copyArray(arr_, arr);

	int maxx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maxx = max(arr[i][j], maxx);
		}
	}

	if (maxx <= L_max[L]) {
		return;
	}

	real_ans = max(real_ans, maxx);

	if (L == 10) {
		if (ans < maxx) {
			ans = maxx;

			int tmp = ans;
			while (L > 0) {
				L_max[L--] = tmp;
				tmp /= 2;
			}
		}
		return;
	}


	else {
		up(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		down(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		Left(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		Right(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	DFS(arr, 0);

	cout << real_ans << '\n';


	return 0;
}

반응형

+ Recent posts