题意
给定 \(n\) 行 \(n\) 列的网格地图 \(g\)，包含空地（.）和障碍（#），其中包括玩家（P）和敌人（E）。敌人会按照玩家 \(k\) 回合前的操作进行移动。记移动到边界外或障碍上为移动失败，移动失败后，此移动不作数。求玩家没有移动失败，且在 \(m\) 轮内，使敌人移动失败恰好 \(hp\) 次的移动序列的方案数。
赛时 DFS 20PTS
赛后
这题是一个很变态的 DP。
状态设计：\(f_{m, px, py, ex, ey, hp}\) 表示第 \(m\) 轮，玩家位于 \((px,py)\)，敌人位于 \((ex,ey)\)，还需移动失败 \(hp\) 次。
显然，直接计算会炸掉（\(O(n^4mhp)\)，约 \(1.6\times10^9\)）
我们思考一下特殊情况：\(k=0\)
此时，玩家和敌人是同步移动的，我们只需要确保玩家不移动失败即可，并且，本题的无效状态数极多，因此，我们可以进行 \(BFS\)，这样可以显著减少状态数，实际测算不超过 \(2\times 10^4\)。同时，我们也可以将 \(f\) 的六维状态通过一个结构体包装起来，用 \(map\) 储存 \(f\) 的值，这样，时空问题我们就都解决了。
状态的转移很简单，利用四连通偏移量 \(dx,dy\)，枚举每个点可以转移到哪些点，然后进行刷表转移。注意判断敌人有没有移动失败，如果移动失败，需要将 \(hp-1\)，并复原位置。
\(k\ne 0\)时，我们仔细思考，敌人和玩家在位置上并没有关系，只在移动上有关系。因此，我们将敌人的移动提前 \(k\) 回合，变为与玩家同步，我们就将问题变为了 \(m-k\) 轮内，满足要求的方案数。但由于敌人的移动被我们提前了，实际上，在敌人移动失败 \(hp\) 次后，我们仍可以移动 \(k\) 轮。为此，我们就需要预处理出数组 \(g_{i,j,x}\)，表示从 \((i,j)\) 开始，移动 \(x\) 轮的移动序列方案书，这与移动 \(x\) 轮到达 \((i,j)\) 的方案数相同，因此转移方式不再赘述。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int N = 55, mod = 1e9 + 7;
struct Node{
int m, px, py, ex, ey, hp;
bool operator< (const Node &W) const{
if (m != W.m) return m < W.m;
if (px != W.px) return px < W.px;
if (py != W.py) return py < W.py;
if (ex != W.ex) return ex < W.ex;
if (ey != W.ey) return ey < W.ey;
return hp < W.hp;
}
};
int T;
int n, m, k, hp;
int px, py, ex, ey;
char g[N][N];
queue<Node> q;
int d[N][N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
map<Node, int> f;
set<Node> st;
int main(){
scanf("%d", &T);
while (T -- ){
scanf("%d%d%d%d", &n, &m, &k, &hp);
for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ){
if (g[i][j] == 'P') px = i, py = j, g[i][j] = '.';
if (g[i][j] == 'E') ex = i, ey = j, g[i][j] = '.';
}
while (!q.empty()) q.pop();
f.clear();
st.clear();
memset(d, 0, sizeof d);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j][0] = 1;
for (int x = 1; x <= k; x ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
for (int y = 0; y < 4; y ++ ){
int sx = i + dx[y], sy = j + dy[y];
if (sx < 1 || sx > n || sy < 1 || sy > n || g[sx][sy] == '#') continue;
// if (i == 4 && j == 5 && k == 2) printf("%d %d\n", sx, sy);
d[i][j][x] = (d[i][j][x] + d[sx][sy][x - 1]) % mod;
}
int ans = 0;
q.push({0, px, py, ex, ey, hp});
f[{0, px, py, ex, ey, hp}] = 1;
while (!q.empty()){
Node t = q.front();
q.pop();
if (!t.hp){
ans = (ans + (LL) f[t] * d[t.px][t.py][k] % mod) % mod;
continue;
}
if (t.m + k == m) continue;
for (int x = 0; x < 4; x ++ ){
int spx = t.px + dx[x], spy = t.py + dy[x];
int sex = t.ex + dx[x], sey = t.ey + dy[x];
int hp = t.hp;
if (spx < 1 || spx > n || spy < 1 || spy > n || g[spx][spy] == '#') continue;
if (sex < 1 || sex > n || sey < 1 || sey > n || g[sex][sey] == '#'){
sex = t.ex, sey = t.ey;
hp -- ;
}
f[{t.m + 1, spx, spy, sex, sey, hp}] = (f[{t.m + 1, spx, spy, sex, sey, hp}] + f[t]) % mod;
if (st.find({t.m + 1, spx, spy, sex, sey, hp}) == st.end()) q.push({t.m + 1, spx, spy, sex, sey, hp}), st.insert({t.m + 1, spx, spy, sex, sey, hp});
}
}
printf("%d\n", ans);
}
}