문제:
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
코드:
초기상태가 최댓값일 수 있음.
숫자 갱신될 때만 max값 갱신하면 됨
#include <iostream>
#include <vector>
#include <algorithm>
#define f(i, n) for(int i = 0; i < (n); ++i)
#define MAP(tp, r, c) ((tp)? nmap[r][c] : nmap[c][r])
using namespace std;
int N;
int ans = 0;
void play(int t, vector<vector<int>> &map) {
if (t == 5) return;
f(d, 4) {
vector<vector<int>> nmap = map;
bool tp; int yb, yd;
switch (d) {
case 0: tp = 0, yb = N - 1, yd = -1; break;
case 2: tp = 0, yb = 0, yd = 1; break;
case 1: tp = 1, yb = 0, yd = 1; break;
case 3: tp = 1, yb = N - 1, yd = -1; break;
}
f(x, N) {
for (int y = yb; 0 <= y && y < N;) {
int y1, y2, y3;
for (y1 = y; 0 <= y1 && y1 < N && !MAP(tp, x, y1); y1 += yd); // 첫번째 숫자
if (y1 < 0 || N <= y1) break;
for (y2 = y1 + yd; 0 <= y2 && y2 < N && !MAP(tp, x, y2); y2 += yd); // 두번째 숫자
int n = MAP(tp, x, y1);
if (0 <= y2 && y2 < N && MAP(tp, x, y1) == MAP(tp, x, y2)) { // 숫자 하나만 존재 or 2개 존재하나 숫자 다름
n <<= 1;
ans = max(ans, n);
MAP(tp, x, y2) = 0;
}
MAP(tp, x, y1) = 0;
for (y3 = y2 - yd; 0 <= y3 && y3 < N && !MAP(tp, x, y3); y3 -= yd);
y3 += yd;
MAP(tp, x, y3) = n;
y = y2;
}
}
if(map != nmap)
play(t + 1, nmap);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
vector<vector<int>> map(N, vector<int>(N));
f(r, N) f(c, N) {
cin >> map[r][c];
ans = max(ans, map[r][c]);
}
play(0, map);
cout << ans;
return 0;
}