종이 조각

Problem link: https://www.acmicpc.net/problem/14391

입력의 크기가 작으므로 간단한 백트래킹을 통해 풀어줄 수 있다.

row major order로 각 위치에 대해서 배치할 수 있는 경우의 수를 한 번씩 시도해주면 된다.

한 편, 가로로 연결한 칸을 1로, 세로로 연결한 칸을 0으로하여 비트마스킹으로도 풀어줄 수 있는데, 입력이 매우 작으므로 굳이 사용하지는 않았다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxH = 4;
const int kMaxW = 4;

int H;
int W;
int PAPER[kMaxH][kMaxW];
int VISIT[kMaxH][kMaxW];

int Assemble(const int row, const int col, const int height, const int width)
{
  int ret = 0;

  for (int h = 0; h < height; ++h)
  {
    for (int w = 0; w < width; ++w)
    {
      ret *= 10;
      ret += PAPER[row + h][col + w];
    }
  }

  return ret;
}

int Solve(const int row, const int col)
{
  const int index = row * W + col;

  if (index >= H * W)
  {
    return 0;
  }

  if (VISIT[row][col])
  {
    return Solve((index + 1) / W, (index + 1) % W);
  }

  int ret = 0;

  // Sole
  VISIT[row][col] = 1;
  ret = max(ret, Assemble(row, col, 1, 1) + Solve((index + 1) / W, (index + 1) % W));
  VISIT[row][col] = 0;

  // Vertical
  for (int h = 2; row + h - 1 < H && VISIT[row + h - 1][col] == 0; ++h)
  {
    for (int hh = 0; hh < h; ++hh)
    {
      VISIT[row + hh][col] = 1;
    }

    ret = max(ret, Assemble(row, col, h, 1) + Solve((index + 1) / W, (index + 1) % W));

    for (int hh = 0; hh < h; ++hh)
    {
      VISIT[row + hh][col] = 0;
    }
  }

  // Horizontal
  for (int w = 2; col + w - 1 < W && VISIT[row][col + w - 1] == 0; ++w)
  {
    for (int ww = 0; ww < w; ++ww)
    {
      VISIT[row][col + ww] = 1;
    }

    ret = max(ret, Assemble(row, col, 1, w) + Solve((index + 1) / W, (index + 1) % W));

    for (int ww = 0; ww < w; ++ww)
    {
      VISIT[row][col + ww] = 0;
    }
  }

  return ret;
}

int main(void)
{
  // Read Input
  scanf(" %d %d", &H, &W);
  for (int r = 0; r < H; ++r)
  {
    for (int c = 0; c < W; ++c)
    {
      scanf(" %1d", &PAPER[r][c]);
    }
  }

  // Solve
  printf("%d\n", Solve(0, 0));

  return 0;
}