题解 - [Luogu P4205] [NOI2005] 智慧珠游戏

发表于 2020-10-25 更新于 2024-06-19 分类于算法竞赛，题解本文字数： 968 阅读时长 ≈ 4 分钟

题目链接

原始题面

1000 ms / 125.00 MB

题目描述

智慧珠游戏拼盘由一个三角形盘件和 12 个形态各异的零件组成。拼盘的盘件如图 1 所示:

12 个零件按珠子数分 3 大类:

第 1 大类，有三个珠子，只有一种形状
- 符号为 A, 形状为
第 2 大类，有 4 个珠子，有 3 种形状
- 符号为 B, 形状为
- 符号为 C, 形状为
- 符号为 D, 形状为
第 3 大类，有 5 个珠子，有 8 种形状
- 符号为 E, 形状为
- 符号为 F, 形状为
- 符号为 G, 形状为
- 符号为 H, 形状为
- 符号为 I, 形状为
- 符号为 J, 形状为
- 符号为 K, 形状为
- 符号为 L, 形状为

图 2 示出了一种拼盘方案。为便于描述可将图 2 抽象为图 3, 就可以用一个数据为字符的二维数组来表示了

对于由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且尺寸合适，所有的零件都允许旋转 (0º、90º、180º、270º) 和翻转 (水平、竖直)

现给出一个盘件的初始布局，求一种可行的智慧珠摆放方案，使所有的零件都能放进盘件中

输入输出格式

输入格式

文件中包含初始的盘件描述，一共有 10 行，第 i 行有 i 个字符。如果第 i 行的第 j 个字符是字母 "A" 至 "L" 中的一个，则表示第 i 行第 j 列的格子上已经放了零件，零件的编号为对应的字母。如果第 i 行的第 j 个字符是 ".", 则表示第 i 行第 j 列的格子上没有放零件。输入保证预放的零件已摆放在盘件中

输出格式

如果能找到解，向输出文件打印 10 行，为放完全部 12 个零件后的布局。其中，第 i 行应包含 i 个字符，第 i 行的第 j 个字符表示第 i 行第 j 列的格子上放的是哪个零件

如果无解，输出单独的一个字符串 'No solution'(不要引号，请注意大小写)

所有的数据保证最多只有一组解

输入输出样例

输入样例 #1

.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........

输出样例 #1

B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF

解题思路

把所有零件视作 4x4 且最上端无空行，最左端无空列的图形，之后把所有可能的图形预处理出来，一共 60 种，对这 60 种图形均尝试能否放入拼盘

状态这样选取:

单次操作为在某位置放某图形，所以总的操作一共 \(55\times 60=3300\) 种，这其中有许多非法操作，记得删掉
用 \(55+12=67\) 维向量表示单次操作后的影响，其中
- \(1\sim 12\) 维表示放了某种零件
- \(13\sim 67\) 维表示零件占据了哪些位置

参考代码里对拼盘和零件的编码方式如下:

Board::data[] 存储拼盘状态，每 4 位表示一个格子，第 r 行第 c 列 (从 0 开始) 格子的状态为 (Board::data[r] >> (4 * (9 - c))) & 15, 0 表示无珠子，f 表示不可放置

如第 4 行状态为 I.ADA 时，Board::data[4] 为 0x90141fffff
pieces[] 为所有零件对应的图形 (包含旋转和对称), 由 20 位构成，其中高 4 位表示零件种类，低 16 位为一个 4x4 图形

如 0x14c00 表示第 A 类零件，用 x 表示有珠子，. 表示无珠子，则图形为
1
2
3
4
.x..
xx..
....
....
零件对应图形的预处理代码参见命名空间 PieceOperation, 调用 PieceOperation::getall() 即可得到 pieces[]

代码参考

Show code

Luogu_P4205view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
class DLX {
protected:
  struct Node {
    size_t l, r, u, d, row, col;
    constexpr Node(size_t l = 0,
                   size_t r = 0,
                   size_t u = 0,
                   size_t d = 0,
                   size_t row = 0,
                   size_t col = 0)
      : l(l), r(r), u(u), d(d), row(row), col(col) {}
    friend std::ostream &operator<<(std::ostream &os, Node const &data) {
      return os << data.l << ' ' << data.r << ' ' << data.u << ' ' << data.d
                << ' ' << data.row << ' ' << data.col;
    }
  };
  std::vector<Node> data;
  std::vector<size_t> cnt_col;
  bool multians;
#define l_(x) data[x].l
#define r_(x) data[x].r
#define u_(x) data[x].u
#define d_(x) data[x].d
#define row_(x) data[x].row
#define col_(x) data[x].col
#define for_(i, start, dir)                                         \
  for (size_t start__ = (start), i = dir##_(start__); i != start__; \
       i = dir##_(i))
  void remove_(size_t col) {
    r_(l_(col)) = r_(col);
    l_(r_(col)) = l_(col);
    for_(i, col, d)
      for_(j, i, r) {
        u_(d_(j)) = u_(j);
        d_(u_(j)) = d_(j);
        --cnt_col[col_(j)];
      }
  }
  void resume_(size_t col) {
    r_(l_(col)) = l_(r_(col)) = col;
    for_(i, col, u)
      for_(j, i, r) {
        u_(d_(j)) = d_(u_(j)) = j;
        ++cnt_col[col_(j)];
      }
  }
  bool dance_(std::vector<size_t> &ans_,
              std::function<void(std::vector<size_t> const &)> const &func_) {
    size_t now = r_(0);
    if (now == 0) return func_(ans_), true;
    for_(i, 0, r)
      if (cnt_col[i] < cnt_col[now]) now = i;
    remove_(now);
    bool ret = false;
    for_(i, now, d) {
      ans_.push_back(row_(i));
      for_(j, i, r) remove_(col_(j));
      ret |= dance_(ans_, func_);
      for_(j, i, l) resume_(col_(j));
      if (!multians && ret) return true;
      ans_.pop_back();
    }
    resume_(now);
    return ret;
  }
  void ins_row_(size_t row, const std::vector<size_t> &cols) {
    assert(row > 0);
    size_t sz = data.size();
    for (size_t i = 0; i < cols.size(); ++i) {
      data.emplace_back(
        sz + i - 1, sz + i + 1, u_(cols[i]), cols[i], row, cols[i]);
      u_(cols[i]) = d_(u_(cols[i])) = sz + i;
      ++cnt_col[cols[i]];
      if (d_(cols[i]) == cols[i]) d_(cols[i]) = sz + i;
    }
    r_(l_(sz) = data.size() - 1) = sz;
  }

public:
  explicit DLX(size_t width, bool multi_ans = false)
    : data(), cnt_col(), multians(multi_ans) {
    reset(width);
  }
  explicit DLX(std::vector<std::vector<bool>> const &grid,
               bool multi_ans = false)
    : data(), cnt_col(), multians(multi_ans) {
    reset_grid(grid);
  }
  friend std::ostream &operator<<(std::ostream &os, DLX const &dlx) {
    os << dlx.data[0].l << ' ' << dlx.cnt_col.size() << ' ' << dlx.data.size()
       << '\n';
    for (size_t i = 1; i < dlx.cnt_col.size(); ++i)
      os << dlx.cnt_col[i] << " \n"[i == dlx.cnt_col.size() - 1];
    for (size_t i = 0; i < dlx.data.size(); ++i)
      os << i << ": " << dlx.data[i] << '\n';
    return os;
  }
  void reset(size_t width) {
    assert(width > 0);
    data.clear();
    cnt_col.resize(width + 1, 0);
    for (size_t i = 0; i <= width; ++i)
      data.emplace_back(i - 1, i + 1, i, i, 0, i);
    r_(l_(0) = width) = 0;
  }
  void reset_grid(std::vector<std::vector<bool>> const &grid) {
    size_t col = grid[0].size();
    for (size_t i = 1; i < grid.size(); ++i)
      col = std::max(col, grid[i].size());
    reset(col);
    std::vector<size_t> _;
    for (size_t i = 0; i < grid.size(); ++i) {
      _.clear();
      for (size_t j = 0; j < grid[i].size(); ++j)
        if (grid[i][j]) _.push_back(j + 1);
      if (!_.empty()) ins_row_(i + 1, _);
    }
  }
  std::pair<bool, std::vector<size_t>>
  dance(std::function<void(std::vector<size_t> const &)> func =
          [](std::vector<size_t> const &) {}) {
    std::vector<size_t> ans;
    return {dance_(ans, func), ans};
  }
#undef l_
#undef r_
#undef u_
#undef d_
#undef row_
#undef col_
#undef for_
};
namespace PieceOperation {
constexpr uint32_t flip4(uint32_t x) {
  return (x & 1) << 3 | ((x >> 1) & 1) << 2 | ((x >> 2) & 1) << 1 |
         ((x >> 3) & 1);
}
constexpr uint32_t expand4(uint32_t x) {
  return (x & 8) << 9 | (x & 4) << 6 | (x & 2) << 3 | (x & 1);
}
constexpr uint32_t flip16(uint32_t x) {
  return flip4((x >> 12) & 15) << 12 | flip4((x >> 8) & 15) << 8 |
         flip4((x >> 4) & 15) << 4 | flip4(x & 15);
}
constexpr uint32_t rot16(uint32_t x) {
  return expand4(flip4((x >> 12) & 15)) << 3 |
         expand4(flip4((x >> 8) & 15)) << 2 |
         expand4(flip4((x >> 4) & 15)) << 1 | expand4(flip4(x & 15));
}
constexpr uint32_t rearrange16(uint32_t x) {
  assert(x);
  while (!(x & 0xf000)) x <<= 4;
  while (!(x & 0x8888))
    x = (((x >> 12) & 7) << 13) | (((x >> 8) & 7) << 9) |
        (((x >> 4) & 7) << 5) | ((x & 7) << 1);
  return x;
}
const uint32_t pieces_base[] = {0x1c800,
                                0x2f000,
                                0x3e800,
                                0x4cc00,
                                0x588e0,
                                0x6f400,
                                0x7ea00,
                                0x8ec00,
                                0x9e300,
                                0xa4e40,
                                0xb8c60,
                                0xcf800};
constexpr uint32_t flip(uint32_t piece) {
  return (piece & 0xf0000) | rearrange16(flip16(piece & 0xffff));
}
constexpr uint32_t rotate(uint32_t piece) {
  return (piece & 0xf0000) | rearrange16(rot16(piece & 0xffff));
}
std::vector<uint32_t> getall() {
  std::set<uint32_t> s;
  for (auto &&i : pieces_base)
    s.merge(std::set<uint32_t>{i,
                               rotate(i),
                               rotate(rotate(i)),
                               rotate(rotate(rotate(i))),
                               flip(i),
                               rotate(flip(i)),
                               rotate(rotate(flip(i))),
                               rotate(rotate(rotate(flip(i))))});
  std::vector<uint32_t> ans;
  for (auto &&j : s) ans.push_back(j);
  return ans;
}
}  // namespace PieceOperation
const uint32_t pieces[60] = {
  0x14c00, 0x18c00, 0x1c400, 0x1c800, 0x28888, 0x2f000, 0x32e00, 0x344c0,
  0x388c0, 0x38e00, 0x3c440, 0x3c880, 0x3e200, 0x3e800, 0x4cc00, 0x522e0,
  0x588e0, 0x5e220, 0x5e880, 0x62f00, 0x644c4, 0x64c44, 0x64f00, 0x688c8,
  0x68c88, 0x6f200, 0x6f400, 0x7ae00, 0x7c4c0, 0x7c8c0, 0x7ea00, 0x84cc0,
  0x86e00, 0x88cc0, 0x8cc40, 0x8cc80, 0x8ce00, 0x8e600, 0x8ec00, 0x93e00,
  0x944c8, 0x94c88, 0x97c00, 0x988c4, 0x98c44, 0x9c700, 0x9e300, 0xa4e40,
  0xb26c0, 0xb6c80, 0xb8c60, 0xbc620, 0xc1f00, 0xc444c, 0xc888c, 0xc8f00,
  0xcc444, 0xcc888, 0xcf100, 0xcf800};
class Board {
protected:
  uint64_t data[10] = {};
  bool pplaced[16] = {};
  uint32_t pcord[16][2] = {{10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10},
                           {10, 10}};

public:
  constexpr Board() = default;
  friend std::istream &operator>>(std::istream &is, Board &board) {
    std::string s;
    for (uint64_t _ = 0xfffffffff, i = 0; i < 10; ++i, _ >>= 4) {
      is >> s;
      board.data[i] = _;
      for (size_t j = 0; j <= i; ++j)
        if (isalpha(s[j])) {
          board.pplaced[s[j] & 15] = true;
          auto &coord = board.pcord[s[j] & 15];
          coord[0] = std::min(coord[0], (uint32_t)i);
          coord[1] = std::min(coord[1], (uint32_t)j);
          board.data[i] |= (s[j] & 15ull) << (4 * (9 - j));
        }
    }
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, Board const &board) {
    uint32_t _;
    for (size_t i = 0; i < 10; ++i) {
      for (size_t j = 0; j <= i; ++j)
        os << ((_ = board.get(i, j)) ? (char)(_ + '@') : '.');
      os << '\n';
    }
    return os;
  }
  constexpr uint32_t get(size_t row, size_t col) const {
    assert(row < 10 && col <= row);
    return (data[row] >> (4 * (9 - col))) & 15;
  }
  constexpr bool can_place_4x4(size_t row, size_t col, size_t piece) const {
    if (row > 9 || col > row) return false;
    auto &&pid = (piece >> 16) & 15;
    if (pplaced[pid]) {
      if (row != pcord[pid][0] || col != pcord[pid][1]) return false;
    } else pid = 0;
    size_t p[4] = {
      (piece >> 12) & 15, (piece >> 8) & 15, (piece >> 4) & 15, piece & 15};
    for (size_t i = 0, s = 0, end_ = !!p[0] + !!p[1] + !!p[2] + !!p[3];
         i < end_;
         ++i) {
      if (row + i > 9) return false;
      ptrdiff_t ofs = 4 * (6 - (ptrdiff_t)col);
      s = (ofs < 0 ? (data[row + i] << -ofs | ((1ull << -ofs) - 1)) :
                     (data[row + i] >> ofs)) &
          0xffff;
      s = (((s >> 12) & 15) == pid) << 3 | (((s >> 8) & 15) == pid) << 2 |
          (((s >> 4) & 15) == pid) << 1 | ((s & 15) == pid);
      if (p[i] & (p[i] ^ s)) return false;
    }
    return true;
  }
  constexpr void place_4x4(size_t row, size_t col, size_t piece) {
    auto &&pid = (piece >> 16) & 15;
    for (size_t i = row; i < std::min((size_t)10, row + 4); ++i)
      for (size_t j = col; j < std::min((size_t)10, col + 4); ++j)
        data[i] |= ((pid * !!(piece & (1 << (15 - (i - row) * 4 - j + col))))
                    << (4 * (9 - j)));
  }
};
int main() {
  Board board;
  cin >> board;
  vector<vector<bool>> maps;
  vector<tuple<size_t, size_t, size_t>> coord;
  {
    auto encode = [](size_t row, size_t col) {
      return 12 + row * (row + 1) / 2 + col;
    };
    vector<bool> _;
    for (size_t id = 0; id < sizeof(pieces) / sizeof(pieces[0]); ++id)
      for (size_t i = 0; i < 10; ++i)
        for (size_t j = 0; j <= i; ++j)
          if (board.can_place_4x4(i, j, pieces[id])) {
            _.clear();
            _.resize(67);
            _[((pieces[id] >> 16) & 15) - 1] = 1;
            for (size_t _i = 0; _i < 4; ++_i)
              for (size_t _j = 0; _j < 4; ++_j)
                _[encode(i + _i, j + _j)] =
                  pieces[id] & (1 << (15 - _i * 4 - _j));
            coord.emplace_back(id, i, j);
            maps.push_back(_);
          }
  }
  auto &&[f, res] = DLX(maps).dance();
  if (!f) {
    cout << "No solution";
    return 0;
  }
  for (auto &&x : res) {
    auto &&[id, i, j] = coord[x - 1];
    board.place_4x4(i, j, pieces[id]);
  }
  cout << board;
  return 0;
}