菜王的 blog

另外一种理解方式。

分别记原题中的 $H, W, N$ 为 $n, m, k$。

先考虑判定：给你一个长为 $2k$ 的串，判断是否能走出这个串。

考虑 DP：$g_{p, i, j}$ 表示匹配了前 $p$ 个位置，是否能到达 $(i, j)$，状态数为 $O(knm)$，可以滚动数组变为 $O(nm)$。

考虑优化，因为每次可以在一行 / 一列内任意走动，所以只需要记录行 / 列。设 $g_{p, i}$ 表示匹配了前 $p$ 个位置，能否走到第 $i$ 行 / 列（$p$ 为偶数时代表行，否则代表列），状态数为 $O(k(n + m))$，可以滚动数组变为 $O(n + m)$。

回到原题，因为 $n, m$ 很小，所以可以直接将 $g$ 记入状态，做 DP 套 DP。即，设 $f_{i, s}$ 表示匹配了前 $i$ 个位置且 $g_i = s$ 的方案数。转移时枚举下一个字符是什么，并同时转移 $g$。

简单预处理即可做到 $O(bk2^{\max(n, m)})$，此处字符集大小 $b = 9$。