对这道题的建模的理解也是一件小有挑战的事情。
题面给的图形是 4 * 4 的一个方格。这里的建模方案如下，
// Overlapping Squares, Xia’an 2006, UVa12113
// 陈锋
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;
struct Grid {
// HEdges 代表的是 32 位二进制的整数
int HEdges, VEdges;
inline void clear() { HEdges = 0, VEdges = 0; }
inline bool getHEdge(int row, int col) const {
return HEdges & (1 << (row * 5 + col)); // 取出 HEdges 的第 (row * 5 + col) 位，这里是以 5 位为一个分隔，在这里其实一共只需要用到前 25 位
}
inline bool getVEdge(int row, int col) const {
return VEdges & (1 << (row * 5 + col)); // 取出 VEdges 的第 (row * 5 + col) 位
}
inline void setHEdge(int row, int col) {
HEdges |= (1 << (row * 5 + col)); // 同样的位，5 个位一个分隔
}
inline void clearHEdge(int row, int col) {
HEdges &= ~(1 << (row * 5 + col)); // 放一个正方形纸片的时候，其内部的十字线需要清除
}
inline void setVEdge(int row, int col) {
VEdges |= (1 << (row * 5 + col)); // 将 gird 重的 row, col 这个点的竖线设置为 1
}
inline void clearVEdge(int row, int col) {
VEdges &= ~(1 << (row * 5 + col)); // 擦除
}
// 初始化
Grid() { clear(); }
// 重载判断符
inline bool operator==(const Grid& g) const { return HEdges == g.HEdges && VEdges == g.VEdges; }
void putSquare(int r, int c) { // 以 r, c 为左上角放一张纸，r, c 是 5 * 5 的 grid 中的一个点的坐标
assert(0 <= r && r <= 2); // row 必须小于 2，否则纸片放不上去
assert(0 <= c && c <= 2); // col 必须小于 2，否则纸片放不上去
setHEdge(r, c), setVEdge(r, c), setHEdge(r, c + 1);
clearVEdge(r, c + 1);
setVEdge(r, c + 2), setVEdge(r + 1, c);
clearHEdge(r + 1, c), clearHEdge(r + 1, c + 1), clearVEdge(r + 1, c + 1);
setVEdge(r + 1, c + 2), setHEdge(r + 2, c), setHEdge(r + 2, c + 1);
cout << "HEdges => " << bitset<32>(HEdges) << ", VEdges => " << bitset<32>(VEdges) << '\\n';
}
};
// 重载 Grid 的输出符号
ostream& operator<<(ostream& os, const Grid& g) {
_for(r, 0, 5) {
_for(c, 0, 5) {
os << ((r && g.getVEdge(r - 1, c)) ? '|' : ' ');
os << (g.getHEdge(r, c) ? '_' : ' ');
}
os << "#" << endl;
}
return os;
}
Grid target; // 根据输入而形成的 Grid
/*
g: 目前已经放好的 Grid 布局
dep : 已经放上去的纸张个数，不超过 6
每一层都有 9 种情况，那么，实际的时间复杂度就是 9 的幂次
*/
bool dfs(const Grid& g, int dep) {
if (g == target) return true;
if (dep >= 6) return false;
_for(r, 0, 3) { // 行只有 0，1，2 这三个位置可以放置
_for(c, 0, 3) { // 列只有 0，1，2 这三个位置可以放置
Grid ng = g; // 继承上一次的 Grid
ng.putSquare(r, c); // 新的局面
if (dfs(ng, dep + 1)) return true;
}
}
return false;
}
int main() {
freopen("./test_cases/uva12113.txt", "r", stdin);
string line;
for (int k = 1;; k++) { // 不停地读入数据
target.clear();
// 根据读入的数据构建名为 target 的 Grid
_for(i, 0, 5) { // 每一次连续读 5 行，i 是行
getline(cin, line);
if (line == "0") return 0; // 结束条件
_for(j, 0, 9) { // j 是列
switch (line[j]) {
case ' ': // 不处理空格
break;
case '_': // 横线只能出现在奇数位
assert(j % 2); // 看是否是位于奇数的位置
target.setHEdge(i, j / 2);
break;
case '|': // 竖线只能出现在偶数位
assert(j % 2 == 0);
target.setVEdge(i - 1, j / 2);
break;
default:
cout << "c = " << line[j] << endl;
assert(false);
}
}
}
Grid g;
bool ans = dfs(g, 0);
cout << "Case " << k << ": " << (ans ? "Yes" : "No") << endl;
}
return 0;
}
// 13978335 12113 Overlapping Squares Accepted C++ 0.102 2014-08-02 02:56:25
对这里的 HEdges 和 VEdges 要着重理解一下，这里是利用了位运算的技巧。因为我们是有 5 * 5 个 Grid 的点，所以，HEdges 中的前 25 位(从低位开始)在这里被征用，其中每 5 个编为一组，举个例子，如果我们想知道 Grid 的第 3 行(从 0 开始)第 2 列(从 0 开始) 的向右延伸的横边是有还是空，那么，我们可以使用这个位运算：
HEdges & (1 << (row * 5 + col))
然后对于代码中的
getEdge()getVEdge()setHEdge()setVEdge()clearHEdge()clearVEdge()我们就很自然地可以理解了。
最后理解一下代码中的 dfs，其实就是遍历所有的放纸片的情况，不难理解。