壹、题目描述 ¶
\(\color{red}{\mathcal{The\;Portal\;Has\;Been\;Distoryed.}}\)
在一张 \(n \times n\) 的网格图上每个格子都有一只蚂蚁。每只蚂蚁将会同时往上下左右 \(4\) 个方向中的某个方向前进一步。一个合法的方案是指所有蚂蚁移动完后仍然在网格内，且每个格子仍然有且仅有一只蚂蚁。并且，蚂蚁的对冲是被禁止的。
请统计出所有合法的方案的总数，数据范围 \(n\le 10\).
贰、题解 ¶
第一道插头 \(\rm DP\)，有被恶心到......
考虑使用轮廓线 \(\rm DP\)，定义几种插头：
-
空插头，值为 \(0\)，就是一个空格子；
-
外插头，值为 \(1\)，是 \(\framebox[2][]{\downarrow}\)；
-
内插头，值为 \(2\)，是 \(\framebox[2]{\uparrow}\)；
定义轮廓线表示已决策格子和未决策格子的分界线，并用一个 \(3\) 进制的数表示轮廓线上从左到右的 \(n+1\) 个插头，举个例子，就是这个样子：
然后，我们定义 \(f(i,j,S)\) 表示考虑到格子 \((i,j)\)，轮廓线上的插头状态为 \(S\) 的情况，不难看出，\(S\) 是一个在 \(3\) 进制下有 \(n+1\) 位的数。
初始状态是下面这两种状态：
前者是 \(f(1,1,(12)_3)\)，后者是 \(f(1,1,(21)_3)\)；
而目标状态就是 \(f(n,n,0)\)；
考虑转移的时候就暴力讨论就可以了，考虑在 \((i,j)(j<n)\) 格子的时候，如果我们要将轮廓线扩展到 \((i,j+1)\)，那么轮廓线会出现什么变化。对于所有的 \(9\) 中情况暴力讨论即可。
对于 \(j=n\) 的情况，涉及换行，第 \(n + 1\) 个插头必须为空插头，然后在最前面插入一个空插头。弄到位运算上就是左移一位，然后去掉最高位，不过转移的前提是最高位为 \(0\).
讨论的时候注意一下细节就行了，各种情况看代码即可。总时间复杂度 \(\mathcal O(n^23^{n+1})\). 注意开 long long.
叁、参考代码 ¶
/** @author Arextre */
#include <bits/stdc++.h>
using namespace std;
#define USING_FREAD
// #define NDEBUG
// #define NCHECK
#include <cassert>
/** その可憐な少女は魔女であり、旅人でした。 ―― そう、私です! */
namespace Elaina {
#define rep(i, l, r) for(int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define drep(i, l, r) for(int i = (l), i##_end_ = (r); i >= i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define whole(v) ((v).begin()), ((v).end())
#define bitcnt(s) (__builtin_popcount(s))
#define y0 FUCK_UP
#define y1 MOTHER_FUCKER
#ifdef NCHECK
# define iputs(Content) ((void)0)
# define iprintf(Content, argvs...) ((void)0)
#else
# define iputs(Content) fprintf(stderr, Content)
# define iprintf(Content, argvs...) fprintf(stderr, Content, argvs)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<class T> inline T fab(T x) { return x < 0 ? -x : x; }
template<class T> inline void getmin(T& x, const T rhs) { x = min(x, rhs); }
template<class T> inline void getmax(T& x, const T rhs) { x = max(x, rhs); }
#ifdef USING_FREAD
inline char qkgetc() {
# define BUFFERSIZE 1 << 20
static char BUF[BUFFERSIZE], *p1 = BUF, *p2 = BUF;
return p1 == p2 && (p2 = (p1 = BUF) + fread(BUF, 1, BUFFERSIZE, stdin), p1 == p2) ? EOF : *p1++;
# undef BUFFERSIZE
}
# define CHARRECEI qkgetc()
#else
# define CHARRECEI getchar()
#endif
template<class T> inline T readret(T x) {
x = 0; int f = 0; char c;
while (!isdigit(c = CHARRECEI)) if(c == '-') f = 1;
for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
return f ? -x : x;
}
template<class T> inline void readin(T& x) {
x = 0; int f = 0; char c;
while (!isdigit(c = CHARRECEI)) if (c == '-') f = 1;
for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
if (f) x = -x;
}
template<class T, class... Args> inline void readin(T& x, Args&... args) {
readin(x), readin(args...);
}
template<class T> inline void writln(T x, char c = '\n') {
if (x < 0) putchar('-'), x = -x;
static int __stk[55], __bit = 0;
do __stk[++__bit] = x % 10, x /= 10; while (x);
while (__bit) putchar(__stk[__bit--] ^ 48);
putchar(c);
}
} // namespace Elaina
using namespace Elaina;
const int maxn = 10;
const int maxs = 177147;
int n;
inline void input() { readin(n); }
/** @brief 1 means leaving & 2 means coming */
ll f[maxn + 5][maxn + 5][maxs + 5];
inline int trans(int s) {
for (int ret = 0; ; ret = ret * 3 + (s % 10), s /= 10)
if (!s) return ret;
}
int sys[20];
inline void prelude() {
sys[0] = 1;
rep (i, 1, 15) sys[i] = sys[i - 1] * 3;
}
inline int Lsh(int val, int pos) {
assert(pos >= 0); assert(pos <= 15);
return val * sys[pos];
}
inline int Rsh(int val, int pos) {
assert(pos >= 0); assert(pos <= 15);
return val / sys[pos];
}
int replace(int s, int p, int v) {
assert(0 <= p); assert(p <= 15);
int x = s / sys[p] % 3;
return s + (v - x) * sys[p];
}
int getp(int s, int p) {
assert(0 <= p); assert(p <= 15);
return Rsh(s, p) % 3;
}
inline void solve() {
f[1][1][trans(21)] = f[1][1][trans(12)] = 1;
int U = sys[n + 1];
rep (i, 1, n) rep (j, 0, n) rep (s, 0, U - 1) if (f[i][j][s]) {
if (j == n) {
if (getp(s, j)) continue; // invalid
f[i + 1][0][Lsh(s, 1) % U] = f[i][j][s];
}
else {
if (getp(s, j) == 0 && getp(s, j + 1) == 0) {
f[i][j + 1][replace(replace(s, j, 2), j + 1, 1)] += f[i][j][s];
f[i][j + 1][replace(replace(s, j, 1), j + 1, 2)] += f[i][j][s];
}
else if (getp(s, j) == 0 && getp(s, j + 1) == 1) {
f[i][j + 1][replace(replace(s, j, 1), j + 1, 0)] += f[i][j][s];
f[i][j + 1][replace(replace(s, j, 0), j + 1, 1)] += f[i][j][s];
}
else if (getp(s, j) == 0 && getp(s, j + 1) == 2) {
f[i][j + 1][replace(replace(s, j, 2), j + 1, 0)] += f[i][j][s];
f[i][j + 1][replace(replace(s, j, 0), j + 1, 2)] += f[i][j][s];
}
else if (getp(s, j) == 1 && getp(s, j + 1) == 0) {
f[i][j + 1][replace(replace(s, j, 1), j + 1, 0)] += f[i][j][s];
f[i][j + 1][replace(replace(s, j, 0), j + 1, 1)] += f[i][j][s];
}
else if (getp(s, j) == 1 && getp(s, j + 1) == 1) ; // invalid
else if (getp(s, j) == 1 && getp(s, j + 1) == 2) {
f[i][j + 1][replace(replace(s, j, 0), j + 1, 0)] += f[i][j][s];
}
else if (getp(s, j) == 2 && getp(s, j + 1) == 0) {
f[i][j + 1][replace(replace(s, j, 2), j + 1, 0)] += f[i][j][s];
f[i][j + 1][replace(replace(s, j, 0), j + 1, 2)] += f[i][j][s];
}
else if (getp(s, j) == 2 && getp(s, j + 1) == 1) {
f[i][j + 1][replace(replace(s, j, 0), j + 1, 0)] += f[i][j][s];
}
else if (getp(s, j) == 2 && getp(s, j + 1) == 2) ; // invalid
}
}
writln(f[n][n][0]);
}
signed main() {
prelude();
input();
solve();
return 0;
}