백준 12100번 2048 (Easy) C++

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

 

한 번의 이동에서 이미 합쳐진 블럭은 또 합쳐질 수 없다는 것을 유의해야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int n;
int ans = 0;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

vector<int> dirs;

vector<vector<int>> MakeCopyBoard(const vector<vector<int>>& original) {
	vector<vector<int>> copyBoard(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyBoard[i][j] = original[i][j];
		}
	}
	return copyBoard;
}

void MoveSimulation(vector<vector<int>>& copyBoard, vector<vector<bool>> &makedNow, int row, int col, int dir) {
	if (copyBoard[row][col] == 0) return;
	int currRow = row;
	int currCol = col;
	while (true) {
		int nextRow = currRow + dRow[dir];
		int nextCol = currCol + dCol[dir];
		if (nextRow < 0 || nextRow >= n) break;
		if (nextCol < 0 || nextCol >= n) break;
		if (makedNow[nextRow][nextCol]) break;
		if (copyBoard[nextRow][nextCol] != 0 && copyBoard[nextRow][nextCol] != copyBoard[currRow][currCol]) break;
		if (copyBoard[nextRow][nextCol] == 0) {
			copyBoard[nextRow][nextCol] = copyBoard[currRow][currCol];
			copyBoard[currRow][currCol] = 0;
		}
		else {
			copyBoard[nextRow][nextCol] *= 2;
			copyBoard[currRow][currCol] = 0;
			makedNow[nextRow][nextCol] = true;
			break;
		}
		currRow = nextRow;
		currCol = nextCol;
	}
}

void MoveSimulation(vector<vector<int>>& copyBoard, int dir) {
	vector<vector<bool>> makedNow(n, vector<bool>(n, false));
	if (dir == 0) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				MoveSimulation(copyBoard, makedNow, i, j, dir);
			}
		}
	}
	else if (dir == 1) {
		for (int j = n - 1; j >= 0; j--) {
			for (int i = 0; i < n; i++) {
				MoveSimulation(copyBoard, makedNow, i, j, dir);
			}
		}
	}
	else if (dir == 2) {
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < n; j++) {
				MoveSimulation(copyBoard, makedNow, i, j, dir);
			}
		}
	}
	else if (dir == 3) {
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				MoveSimulation(copyBoard, makedNow, i, j, dir);
			}
		}
	}
}

void BT(const vector<vector<int>> &board) {
	if (dirs.size() >= 5) {
		vector<vector<int>> copyBoard = MakeCopyBoard(board);
		for (auto a : dirs) {
			MoveSimulation(copyBoard, a);
		}
		int maxBlock = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				maxBlock = max(maxBlock, copyBoard[i][j]);
			}
		}
		ans = max(ans, maxBlock);
		return;
	}
	for (int i = 0; i < 4; i++) {
		dirs.push_back(i);
		BT(board);
		dirs.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	vector<vector<int>> board(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	BT(board);
	cout << ans;
};