考虑一个横向单调数列 \(a<b<c\) 如何形成，我们从小到大填数，填到 \(b\) 时，假设 \(b\) 填在 \((x,y)\) 处：若 \((x,y-1),(x,y+1)\) 两个格子上恰有一个位置有值就寄了。纵向的单调数列类似。
于是填数的过程中，我们只关心每个格子上有/没有数。如果这个格子横向或纵向的相邻两个格子上存在以上说的情况，就寄了。这启示我们状态压缩。
令 \(f_{S}\) 为目前格子上面是否有数的状态为 \(S\) 的方案数，由于不合法的状态较多，可以刷表转移。注意到从 \(f_S\) 转移出去时，我们已经填了 \(|S|\) 个数，于是考虑第 \(|S|+1\) 个数放哪即可。
复杂度 \(O(n2^n)\)。