백준 12094번: 2048 (EASY)

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

12100번: 2048 (Easy)

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

int n, arr[21][21], ans = 0;



void print(int arr[][21]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}

	cout << "---------------------------------\n";
	return;
}

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];
		}
	}
}

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

	int arr_[21][21];
	copyArray(arr_, arr);

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

	}
	else {
		up(arr_);
		DFS(arr_, L + 1);

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


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

		copyArray(arr_, arr);
		Right(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 << ans << '\n';
	return 0;
}

 

백준 12100번 2048