BOJ12100: 2048 Easy

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (15/187)
  • 아주우 그지같은 구현문제
  • 그치만 한방에 맞춤 크하하
  • 사실 구현하다가 한 3번은 때려쳤음. 하다가 빡쳐서 딴문제 품
  • 일단 130줄 짜리 코딩을 했다는것에 의의를 둠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;

struct Block {
  int value, merged;
};
Block* board[20][20];

int N, tmp, ans;
enum Dir { UP, DOWN, LEFT, RIGHT };
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};

void copy(Block* to[20][20], Block* from[20][20]) {
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      to[i][j] = from[i][j] ? new Block(*from[i][j]) : nullptr;
}

void del(Block* b[20][20]) {
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      delete b[i][j];
}

bool bound(int n) {
  return n >= 0 && n < N;
}

bool moveInner(int dir, int x, int y) {
  if(!board[x][y]) return false;
  bool move = false;
  board[x][y]->merged = 0;
  while(1) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if(!bound(nx) || !bound(ny)) break;
    if(!board[nx][ny]) {
      board[nx][ny] = board[x][y];
      board[x][y] = nullptr;
    } else if(
        board[nx][ny]->merged ||
        board[x][y]->merged ||
        board[x][y]->value != board[nx][ny]->value) {
      break;
    } else {
      delete board[x][y];
      board[x][y] = nullptr;
      board[nx][ny]->value *= 2;
      board[nx][ny]->merged = 1;
      ans = max(ans, board[nx][ny]->value);
    }
    move = true;
    x = nx, y = ny;
  }
  return move;
}

bool move(int dir) {
  bool move = false;
  if(dir == UP || dir == LEFT) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(moveInner(dir, i,j)) move = true;
      }
    }
  } else {
    for(int i = N-1; i >= 0; i--) {
      for(int j = N-1; j >= 0; j--) {
        if(moveInner(dir, i,j)) move = true;
      }
    }
  }
  return move;
}

void input() {
  cin >> N;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> tmp;
      ans = max(ans, tmp);
      if(!tmp) continue;
      board[i][j] = new Block({tmp, 0});
    }
  }
}

void print() {
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(!board[i][j]) printf("%4d", 0);
      else printf("%4d", board[i][j]->value);
    }
    printf("\n");
  }
}

void go(int n) {
  /* printf("Run %d\n" , n); */
  /* print(); */
  /* printf("\n\n\n"); */
  if(n == 5) return;
  Block* bak[20][20];
  copy(bak, board);
  for(int dir = 0; dir < 4; dir++) {
    bool ret = move(dir);
    if (ret) {
      go(n+1);
    }
    del(board);
    copy(board, bak);
  }
  del(bak);
}


int main() {
  input();
  go(0);
  cout << ans;
}