题目描述

Smith在P市的邮政局工作，他每天的工作是从邮局出发，到自己所管辖的所有邮筒取信件，然后带回邮局。他所管辖的邮筒非常巧地排成了一个$m \times n$的点阵（点阵中的间距都是相等的）。左上角的邮筒恰好在邮局的门口。 Smith是一个非常标新立异的人，他希望每天都能走不同的路线，但是同时，他又不希望路线的长度增加，他想知道他有多少条不同的路线可走。你的程序需要根据给定的输入，给出符合题意的输出。输入包括点阵的$m$和$n$的值，你需要根据给出的输入，计算出Smith可选的不同路线的总条数。

输入格式

只有一行。包括两个整数$m,n(1 \le m \le 10,1 \le n \le 20)$，表示了Smith管辖内的邮筒排成的点阵。

输出格式

只有一行，只有一个整数，表示Smith可选的不同路线的条数。

题目解析

这是插头DP的经典入门题了吧。题目所求即为网格图上经过所有点的哈密顿回路数量$\times 2$。

我们采用括号表示法来表示状态。$'('$表示左插头，$')'$表示右插头，$'\#'$表示无插头。

状态的转移比较复杂，需要仔细分析。设当前决策格的左侧和上侧的插头为$(a,b)$，则有

1.$('\#','\#')$ : 左侧和上侧都没有插头连入。因为每个格子必有两个插头，故向下、向右有插头，也就是开始一个新的连通分量，转移到$('(',')')$。

2.$('(','\#')$ : 左侧有插头连入，上侧没有。我们只需延续原来的连通分量，可以继续向右延伸转移到$('\#','(')$，也可以转向下延伸转移到$('(','\#')$，注意边界情况。

3.$(')','\#')$ : 类似2处理方式。

4.$('\#','(')$ : 上侧有插头连入，左侧没有。处理方式同2,3。

5.$('\#',')')$ : 类似4处理方式。

6.$('(',')')$ : 左侧有左括号插头连入，上侧有有右括号插头连入。那么把它们连起来就圆满啦，刚好构成一条回路。但是注意这种情况只可发生在最后的格子（右下角），此时需要更新答案。

7.$('(','(')$ : 左侧和上侧都有左括号插头连入。这时我们在合并两个联通分量，将它们连起来后，原来与上侧插头相匹配的右括号插头应该变成左括号插头，于是我们找到与上侧插头相匹配的右括号插头修改一下状态即可。

8.$(')',')')$ : 左侧和上侧都有右括号插头连入。处理方式类似7，找到与左侧插头相匹配的左括号插头修改一下状态。

9.$(')','(')$ : 左侧有右括号插头连入，上侧有左括号插头连入。就是将两连通分量连接起来，转移到$('\#','\#')$。

时间复杂度$O(nm 3 ^ m)$。膜一膜CDQ的著名论文《基于连通性状态压缩的动态规划问题》。