插头dp问题

解题思路：

本题如果没有障碍的限制，就是一个求哈密顿回路的问题。我们可以用状态压缩 $dp$ 来求。

如果是求一张图上的哈密顿路径，那么我们可以设 $f_{s,i}$ 表示当前每个点的状态为 $s$，且目前到达点 $i$ 的路径数量。其中 $s$ 为二进制串，每一位记录每个点是否在路径上。

如果只有 $n$ 个点，那么时间复杂度就是 $2^n \times n^2$，可以过，但是由于本题是一个矩阵，因此点数是 $n^2$ 个，那么此时时间复杂度就是 $2^{n^2} \times n^4$，肯定会超时。

而由于是一个矩阵，每个格子只能和上、下、左、右四个格子相连，因此我们可以一行一行的来枚举状态。

但是我们还有一个障碍的限制，由于本题是一个棋盘上的哈密顿回路问题，其实就是一个棋盘上的连通性的状态压缩问题，这一类问题是状态压缩 $dp$ 的一类，是用插头 $dp$ 来解决的。

插头 $dp$ 一般都是在棋盘上设计的一个问题，并且递推的时候一般按格递推，这样时间效率会更高一些。

例如本题，如果按格子来递推，由于求的是一个回路，因此每个格子只有一条入边和一条出边，而每个格子只有四条边，从四条边中选两条边只有 $C_4^2 = 6$ 种情况。但是如果按行来递推，对于当前行每个格子都有 $6$ 种情况，如果直接枚举当前行所有情况，就会有 $6^n$ 种情况，数量非常庞大。显然按格子来递推效率更高。

加上当前需要递推 $(i,j)$ 的状态，此时第 $i$ 行的前 $j-1$ 个格子已经递推完了，前 $i-1$ 行的所有格子也已经递推完了。那么我们未来会用到的情况，应该是递推完的格子和没递推完的格子交接位置上的情况，也就是看一下边界上每个格子有没有一条路径出来。然后由于最终只能有一整条路径，也就是只有一个连通块，因此我们还要维护一下每条出来的边是属于那个连通块的。

这里记录连通性有两种做法，一种是最小表示法，就是从左往右依次遍历所有出来的边，如果当前边所在的连通块没有编号，我们就给他一个编号。如果某一个位置没有出来的边，就将它的编号标记为 $0$。如果某个位置出来的边所在的连通块已经有编号，那么它就是这个编号。

一种是括号表示法，我们观察一下分界线，分界线上一定有很多很多边出来，由于本题求的是回路，因此对于上面已经递推完的部分来说，有一条边上去就一定有一条边下来，因此所有出来的边必然是两两配对的。并且由于是一个网格图，是一个平面，因此每两条路径之间是不存在相交的。有了这两个性质之后，那么所有的路径其实本质上就是一个括号序列，对于每条路径，左边出来的边看成左括号，记为 $1$，右边出来的边看成右括号，记为 $2$，没有边的位置记为 $0$，那么我们就可以用一个只有 $0,1,2$ 的三进制状态将分界线上所有路径表示出来。

括号表示法的适用范围比最小表示法要小，能用最小表示法的不一定能括号表示法，能用括号表示法的一定能用最小表示法。但是括号表示法的状态只有三进制，最小表示法的编号则非常多，而且我们还可以将括号表示法的三进制状态填成四进制状态，然后用位运算去优化，因此括号表示法的效率要比最小表示法更高一些。因此能用括号表示法就尽量用括号表示法，不能用括号表示法再用最小表示法。

本题已经分析出来能用括号表示法，因此我们就用括号表示法来表示分界线上的所有状态。

然后我们考虑状态表示，设 $f_{i,j,S}$ 表示当前递推到 $(i,j)$，且递推完的格子和没有递推的格子之间的分界线的状态是 $S$ 的哈密顿回路的方案数。

这里还有一个特点就是虽然分界线的状态是一个三进制数，看上去最多有 $3^{n+1}$ 种情况，但是我们真正需要考虑的只有满足括号序列的情况，如本题 $n=12$，$3^{n+1}$ 有一百多万种情况，但是去实际计算满足括号序列的情况，其实只有四五万种情况，这也是插头 $dp$ 实际运行的时候效率很高的一个重要原因。

接下来就是插头 $dp$ 的一个重点，考虑状态转移，插头 $dp$ 的状态转移一般都是要分成很多种情况来考虑，非常的麻烦。

设当前递推到的格子是 $(i,j)$，我们令 $(i,j)$ 左边这条边的状态是 $x$，上面这条边的状态是 $y$，下面这条边的状态是 $z$，右边这条边的状态是 $w$，设当前分界线的状态是 $state$。

第一种情况：如果 $(i,j)$ 是障碍物，那么 $(i,j)$ 一定不能经过，此时 $x$ 和 $y$ 只能是 $0$，意味着不能有边走到 $(i,j)$，否则就就能转移。如果 $x,y$ 都是 $0$，此时递推完之后其他边都没有受影响，只有 $x$ 和 $y$ 不在分界线上了，变成了 $z$ 和 $w$，由于 $(i,j)$ 不能经过，因此 $z$ 和 $w$ 同样不能有边出来，所以 $z$ 和 $w$ 也必须是 $0$，而这两条边的状态原本就是 $0$，因此递推完后的状态其实还是 $state$，没有变化。

第二种情况：如果 $x,y$ 都是 $0$，由于 $(i,j)$ 是障碍物的情况已经处理完，因此此时 $(i,j)$ 已经不是障碍物，那么这个格子就必须用到，它需要一条出边和一条入边，但是此时 $x,y$ 都是 $0$，因此我们只能用 $z$ 和 $w$，因此 $z$ 和 $w$ 应该一个是 $1$ 一个是 $2$，由于递推完之后 $x$ 和 $y$ 刚好对应 $z$ 和 $w$，因此递推完后的状态就是将 $state$ 中的 $x,y$ 位置上的状态变成 $1,2$。注意，这里要想将 $z$ 和 $w$ 改成 $1,2$，则 $(i,j)$ 的下面和右边都不能有障碍物。

第三种情况：如果 $x$ 是 $0$，$y$ 不是 $0$，此时说明 $y$ 进来了一条边，就必须还有一条出去的边，此时 $z$ 和 $w$ 都能用，因此要分别枚举一下从 $z$ 和 $w$ 出去的情况，对应的更新一下状态

第四种情况：如果 $x$ 不是 $0$，$y$ 是 $0$，此时说明 $x$ 进来了一条边，就必须还有一条边出去，此时 $z$ 和 $w$ 都能用，因此分别枚举一下从 $z$ 和 $w$ 出去的情况，对应的更新状态

第五种情况：如果 $x,y$ 都是 $1$，则此时 $x$ 和 $y$ 都是各自所在路径的左端点，他们的右边都分别有一个右端点，由于 $x$ 和 $y$ 此时都进入了 $(i,j)$，因此这两条边就连上了，此时 $x$ 和 $y$ 所在的路径变成了一条，那么右边的两个右端点中靠左的那个右端点就应该变成左端点，因此此时需要将 $x$ 原本所在的路径的右端点的状态改为 $1$。而递推完后 $x$ 和 $y$ 会变成 $z$ 和 $w$，$z$ 和 $w$ 已经没有边了，所以要将这两个位置改回 $0$。

第六种情况：如果 $x,y$ 都是 $2$，则此时 $x$ 和 $y$ 都是各自所在路径的右端点，他们的左边都分别有一个左端点，由于 $x$ 和 $y$ 此时都进入了 $(i,j)$，因此这两条边就连上了，此时 $x$ 和 $y$ 所在的路径变成了一条，那么左边的两个左端点中靠右的那个左端点就应该变成右端点，因此此时需要将 $y$ 原本所在的路径的左端点的状态改为 $2$。而递推完后 $x$ 和 $y$ 会变成 $z$ 和 $w$，$z$ 和 $w$ 已经没有边了，所以要将这两个位置改回 $0$。

第七种情况：如果 $x$ 是 $2$，$y$ 是 $1$，则此时 $x$ 是它所在路径的右端点，$y$ 是它所在路径的左端点，$x$ 的左边有一个左端点，$y$ 的右边有一个右端点，由于 $x$ 和 $y$ 此时都进入了 $(i,j)$，因此这两条边就连上了，此时 $x$ 和 $y$ 所在的路径变成了一条，可以发现合并前 $x$ 所在路径的左端点恰好就是合并后路径的左端点，合并前 $y$ 所在路径的右端点，恰好就是合并后路径的右端点。因此这些位置都不需要额外变动。而递推完后 $x$ 和 $y$ 会变成 $z$ 和 $w$，$z$ 和 $w$ 已经没有边了，所以要将这两个位置改回 $0$。

第八种情况：如果 $x$ 是 $1$，$y$ 是 $2$，则此时 $x$ 是它所在路径的左端点，$y$ 是它所在路径的右端点，$x$ 的右边有一个右端点，$y$ 的左边有一个左端点，此时要让路径之间不相交，那么只有一种可能就是 $x$ 和 $y$ 属于同一条路径，此时 $x$ 和 $y$ 同时进入到 $(i,j)$，他们就会连上，由于他们已经在同一条路径中，再连上就会形成回路，因此这种情况恰好就是最终形成回路的一步，所以这一步只会发生在最后一个合法格子中，我们只需要在这个位置统计一下总方案数即可。

以上就是本题的所有情况的状态转移。然后由于我们状态存储的是四进制的括号序列，因此状态表示的第三维最大会有 $4^{12}$ 种情况，但是实际上有效的状态只有四万多个，因此插头 $dp$ 存储状态的时候一般用哈希表来存储，而且由于插头 $dp$ 一般常数比较大，时间卡的比较严，所以一般需要手写哈希表。并且一般插头 $dp$ 的状态数量也比较多，因此一般也会需要用到滚动数组来优化空间，而本题状态没那么多，因此可以不用。

由于第三维的有效状态只是所有状态中极小的一部分，因此我们可以将所有有效状态存储起来，不用每次将所有状态都枚举一遍。

设有效状态数量为 $S$，则插头 $dp$ 递推的时间复杂度就是 $O(Sn^2)$，并且每次递推最坏情况像情况五和情况六，我们都需要枚举一遍分界线来更新状态，这里最坏是 $O(n)$ 的，因此整个的时间复杂度为 $O(Sn^3)$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 50010, M = N * 2 + 7;

int n, m;
int g[20][20]; //地图
int q[2][N]; //q 表示每次滚动的有效状态在哈希表中的下标
int cnt[N]; //cnt 表示每次滚动的有效状态的数量
int h[2][M]; //h 表示滚动哈希表
LL v[2][M]; //v 表示哈希表中每个状态对应的方案数
int end_x, end_y; //记录最后一个合法格子的位置

int find(int cur, int x) //开放寻址法找 x 的位置，cur 表示当前滚动的位置
{
    int t = x % M;
    while(h[cur][t] != -1 && h[cur][t] != x)
        if(++t == M)
            t = 0;
    return t;
}

void insert(int cur, int state, LL w) //将 state 插入到哈希表中，w 表示 state 的方案数
{
    int t = find(cur, state);
    if(h[cur][t] == -1) //如果哈希表中不存在，说明是一个新状态
    {
        h[cur][t] = state, v[cur][t] = w; //插入哈希表
        q[cur][++cnt[cur]] = t; //插入队列
    }
    else v[cur][t] += w; //否则说明已经在哈希表中，直接更新该状态的方案数
}

int get(int state, int k) //求第 k 个格子的状态（求四进制的第 k 位数字）
{
    return state >> k * 2 & 3;
}

int set(int k, int v) //构造一个四进制表示下第 k 位数字是 v 的数
{
    return v * (1 << k * 2);
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        char str[20];
        scanf("%s", str + 1);
        for(int j = 1; j <= m; j++)
            if(str[j] == '.')
            {
                g[i][j] = 1; //1 表示空地，0 表示障碍
                end_x = i, end_y = j; //记录最后一个合法格子的位置
            }
    }

    LL res = 0;
    memset(h, -1, sizeof h); //初始化哈希表
    int cur = 0; //记录当前滚动数组用到第几维
    insert(cur, 0, 1); //最开始一条边都没有，状态是 0，方案数是 1
    for(int i = 1; i <= n; i++)
    {
        //每次枚举完一整行，我们需要将行末的所有状态转化成行首的状态
        //行末是 0.....，行首是 ......0，相当于将每个状态在四进制表示下左移一位
        for(int j = 1; j <= cnt[cur]; j++)
            h[cur][q[cur][j]] <<= 2;

        for(int j = 1; j <= m; j++)
        {
            int last = cur; //记录当前行的状态是滚动数组中第几维
            cur ^= 1, cnt[cur] = 0;
            memset(h[cur], -1, sizeof h[cur]);
            for(int k = 1; k <= cnt[last]; k++)
            {
                int state = h[last][q[last][k]]; //记录当前状态
                LL w = v[last][q[last][k]];
                int x = get(state, j - 1), y = get(state, j); //记录当前格子的左边和上面的状态
                if(!g[i][j]) //如果当前格子是障碍物
                {
                    if(!x && !y) insert(cur, state, w); //情况 1
                }
                else if(!x && !y) //情况 2
                {
                    if(g[i + 1][j] && g[i][j + 1])
                        insert(cur, state + set(j - 1, 1) + set(j, 2), w);
                }
                else if(!x && y) //情况 3
                {
                    if(g[i][j + 1]) insert(cur, state, w);
                    if(g[i + 1][j]) insert(cur, state + set(j - 1, y) - set(j, y), w);
                }
                else if(x && !y) //情况 4
                {
                    if(g[i][j + 1]) insert(cur, state - set(j - 1, x) + set(j, x), w);
                    if(g[i + 1][j]) insert(cur, state, w);
                }
                else if(x == 1 && y == 1) //情况 5
                {
                    //往右找到弟一个右端点变成 1
                    for(int u = j + 1, s = 1; ; u++)
                    {
                        int z = get(state, u);
                        if(z == 1) s++;
                        else if(z == 2)
                        {
                            if(--s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) - set(u, 1), w);
                                break;
                            }
                        }
                    }
                }
                else if(x == 2 && y == 2) //情况 6
                {
                    //往左找到第一个左端点变成 2
                    for(int u = j - 2, s = 1; ; u--)
                    {
                        int z = get(state, u);
                        if(z == 2) s++;
                        else if(z == 1)
                        {
                            if(--s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) + set(u, 1), w);
                                break;
                            }
                        }
                    }
                }
                else if(x == 2 && y == 1) //情况 7
                {
                    insert(cur, state - set(j - 1, x) - set(j, y), w);
                }
                else if(i == end_x && j == end_y) //情况 8
                    res += w;
            }
        }
    }
    printf("%lld\n", res);

    return 0;
}