[BOJ]2100号2048(Easy)c++

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

質問する
2048ゲームは4×4サイズの碁盤で独自に楽しむ面白いゲーム.このリンクをクリックするとゲームができます.このゲームでは、1回の移動は、ボード上のブロック全体を上下左右4方向の1つに移動します.同じ値を持つ2つのブロックが衝突すると、2つのブロックが1つに結合されます.1回の移動では、マージされたブロックは別のブロックと再マージできません.(実際のゲームでは、移動するたびにブロックが追加されますが、この問題ではブロックは追加されません)

<図1>では、ブロックを上に移動すると<図2>の状態となる.ここで、ブロックを左に移動すると<図3>の状態となる.

<図4>の状態で、ブロックを右へ<図5>に移動し、ここでさらに上へ移動するブロックは<図6>である.ここから1ブロック右に移動すると、<図7>が生成されます.

<図8>の状態でブロックを左に移動したらどうなりますか?2は衝突しているので4に統合されて『図9』の状態になります.

<図10>でブロックを上に移動すると<図11>の状態となる.<図12においては、1回の移動中にマージされたブロックがマージされないため、ブロックを上へ移動すると<図13>の状態となる.

最後に、同じ数が3つある場合は、移動するセルを最初にマージします.たとえば、上に移動すると、上のブロックが最初に結合されます.<図14>のように、上に移動すると<図15>が作成される.
この問題に関連する2048ゲームのマザーボードのサイズはNです.×Nです.回路基板のサイズと回路基板のブロック状態が指定されている場合は、最大5回まで移動できるプログラムを作成します.
入力します.
3
2 2 2
4 4 4
8 8 8
出力します.
16

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int N;
int board[6][20][20];
bool visit[20][20] = {false,};
int maxval = 0;
bool flag;

void init(int x) {
  memcpy(board[x], board[x - 1], sizeof(board[0]));
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      visit[i][j] = false;
    }
  }
}

void y_visit(int y, int z, int w) {
  visit[y][w] = false;
  visit[z][w] = true;
}

void x_visit(int y, int z, int w) {
  visit[w][y] = false;
  visit[w][z] = true;
}

int move(int x, int dir) {
  flag = false;
  init(x);

  switch(dir) {
    case 0:
      for(int i = N - 2; i >= 0; i--) {
        for(int j = 0; j < N; j++) {
          if(board[x][i + 1][j] > 0 && board[x][i][j] == 0) {
            board[x][i][j] = board[x][i + 1][j];
            if(visit[i + 1][j])
            y_visit(i + 1, i, j);
            flag = true;

            for(int k = i + 1; k < N - 1; k++) {
              board[x][k][j] = board[x][k + 1][j];
              visit[k][j] = visit[k + 1][j];
            }
            board[x][N - 1][j] = 0;
            visit[N - 1][j] = false;
          }
        }
      }
      for(int i = 0; i < N - 1; i++) {
        for(int j = 0; j < N; j++) {
          if(board[x][i + 1][j] > 0) {
            if((board[x][i + 1][j] == board[x][i][j]) && !visit[i + 1][j] && !visit[i][j]) {
              board[x][i][j] = board[x][i + 1][j] + board[x][i][j];
              maxval = max(maxval, board[x][i][j]);
              y_visit(i + 1, i, j);
              flag = true;

              for(int k = i + 1; k < N - 1; k++) {
                board[x][k][j] = board[x][k + 1][j];
                visit[k][j] = visit[k + 1][j];
              }
              board[x][N - 1][j] = 0;
              visit[N - 1][j] = false;
            }
          }
        }
      }
      break;

    case 1:
      for(int i = 1; i < N; i++) {
        for(int j = 0; j < N; j++) {
          if(board[x][i - 1][j] > 0 && board[x][i][j] == 0) {
            board[x][i][j] = board[x][i - 1][j];
            if(visit[i - 1][j])
            y_visit(i - 1, i, j);
            flag = true;

            for(int k = i - 1; k > 0; k--) {
              board[x][k][j] = board[x][k - 1][j];
              visit[k][j] = visit[k - 1][j];
            }
            board[x][0][j] = 0;
            visit[0][j] = false;
          }
        }
      }
      for(int i = N - 1; i > 0; i--) {
        for(int j = 0; j < N; j++) {
          if(board[x][i - 1][j] > 0) {
            if((board[x][i - 1][j] == board[x][i][j]) && !visit[i - 1][j] && !visit[i][j]) {
              board[x][i][j] = board[x][i - 1][j] + board[x][i][j];
              maxval = max(maxval, board[x][i][j]);
              y_visit(i - 1, i, j);
              flag = true;

              for(int k = i - 1; k > 0; k--) {
                board[x][k][j] = board[x][k - 1][j];
                visit[k][j] = visit[k - 1][j];
              }
              board[x][0][j] = 0;
              visit[0][j] = false;
            }
          }
        }
      }
      break;

    case 2:
      for(int j = N - 2; j >= 0; j--) {
        for(int i = 0; i < N; i++) {
          if(board[x][i][j + 1] > 0 && board[x][i][j] == 0) {
            board[x][i][j] = board[x][i][j + 1];
            if(visit[i][j + 1])
              x_visit(j + 1, j, i);
            flag = true;

            for(int k = j + 1; k < N - 1; k++) {
              board[x][i][k] = board[x][i][k + 1];
              visit[i][k] = visit[i][k + 1];
            }
            board[x][i][N - 1] = 0;
            visit[i][N - 1] = false;
          }
        }
      }
      for(int j = 0; j < N - 1; j++) {
        for(int i = 0; i < N; i++) {
          if(board[x][i][j + 1] > 0) {
            if((board[x][i][j + 1] == board[x][i][j]) && !visit[i][j + 1] && !visit[i][j]) {
              board[x][i][j] = board[x][i][j + 1] + board[x][i][j];
              maxval = max(maxval, board[x][i][j]);
              x_visit(j + 1, j, i);
              flag = true;

              for(int k = j + 1; k < N - 1; k++) {
                board[x][i][k] = board[x][i][k + 1];
                visit[i][k] = visit[i][k + 1];
              }
              board[x][i][N - 1] = 0;
              visit[i][N - 1] = false;
            }
          }
        }
      }
      break;

    case 3:
      for(int j = 1; j < N; j++) {
        for(int i = 0; i < N; i++) {
          if(board[x][i][j - 1] > 0 && board[x][i][j] == 0) {
            board[x][i][j] = board[x][i][j - 1];
            if(visit[i][j - 1])
              x_visit(j - 1, j, i);
            flag = true;

            for(int k = j - 1; k > 0; k--) {
              board[x][i][k] = board[x][i][k - 1];
              visit[i][k] = visit[i][k - 1];
            }
            board[x][i][0] = 0;
            visit[i][0] = false;
          }
        }
      }
      for(int j = N - 1; j > 0; j--) {
        for(int i = 0; i < N; i++) {
          if(board[x][i][j - 1] > 0) {
            if((board[x][i][j - 1] == board[x][i][j]) && !visit[i][j - 1] && !visit[i][j]) {
              board[x][i][j] = board[x][i][j - 1] + board[x][i][j];
              maxval = max(maxval, board[x][i][j]);
              x_visit(j - 1, j, i);
              flag = true;

              for(int k = j - 1; k > 0; k--) {
                board[x][i][k] = board[x][i][k - 1];
                visit[i][k] = visit[i][k - 1];
              }
              board[x][i][0] = 0;
              visit[i][0] = false;
            }
          }
        }
      }
      break;
  }

  return flag;
}

void num(int x) {
  if(x == 6)
    return;
  for(int dir = 0; dir < 4; dir++) {
    if(!move(x, dir))
      continue;
    num(x + 1);
  }
}

int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      scanf("%d", &board[0][i][j]);
      maxval = max(maxval, board[0][i][j]);
    }
  }

  num(1);
  printf("%d\n", maxval);
}

最大5回まで移動可能で、再帰関数を使用して移動回数を増やします.
4つの方向を方向1,2,3,4と呼ぶ.K(0ブロック移動の場合は2種類あります.ブロックが空の場合は移動可能で、移動方向が同じ場合はマージされます.ただし、後者の場合、上記<図14>の条件と、1回の移動でマージされたブロックとは、マージできないことを覚えておいてください.私は別の2つの状況を計算した.スイッチドアの条件は方向を表し,各方向に2つの二重複文がある.1つ目はブロックが空であるために移動し、2つ目は同じ数字があればマージします.次に、ブロックをマージするたびにmaxval値と比較し続けると、最大のブロックが得られます.
4時間ぐらいかかりました.コードが汚いのですが、今日はもうやりたくないのでアップしました.Easyバージョンは私にとっても難しいです.Hardバージョンも次回にリリースします.😐