LibreOJ 2178 「BJOI2017」机动训练

考虑将平方看做组合意义：两个人走地形序列相同的路径的方案数。

对于方向的问题，可以将方向分为四类：左、上、左上；右、上、右上；左、下、左下；右、下、右下。
那么一条路径一定是一直走同类方向的。
然而一直向左、上、右、下的路径会被算重，于是再减去即可。

使用记搜实现（否则较难确定转移顺序）。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 30;
const int mod = 1e9 + 9;
int n,m;
char a[N + 5][N + 5];
int dx[2],dy[2];
int f[N + 5][N + 5][N + 5][N + 5];
int dfs(int x1,int y1,int x2,int y2)
{
    if(x1 < 1 || x1 > n || y1 < 1 || y1 > m || x2 < 1 || x2 > n || y2 < 1 || y2 > m)
        return 0;
    if(a[x1][y1] ^ a[x2][y2])
        return 0;
    if(~f[x1][y1][x2][y2])
        return f[x1][y1][x2][y2];
    int ret = 1;
    for(register int i1 = -1;i1 <= 1;++i1)
        if(!i1 || i1 == dx[0])
            for(register int j1 = -1;j1 <= 1;++j1)
                if((i1 || j1) && (!j1 || j1 == dy[0]))
                    for(register int i2 = -1;i2 <= 1;++i2)
                        if(!i2 || i2 == dx[1])
                            for(register int j2 = -1;j2 <= 1;++j2)
                                if((i2 || j2) && (!j2 || j2 == dy[1]))
                                    ret = (ret + dfs(x1 + i1,y1 + j1,x2 + i2,y2 + j2)) % mod;
    return f[x1][y1][x2][y2] = ret;
}
inline int calc(int dx1,int dy1,int dx2,int dy2)
{
    memset(f,-1,sizeof f);
    dx[0] = dx1,dy[0] = dy1,dx[1] = dx2,dy[1] = dy2;
    int ret = 0;
    for(register int x1 = 1;x1 <= n;++x1)
        for(register int y1 = 1;y1 <= m;++y1)
            for(register int x2 = 1;x2 <= n;++x2)
                for(register int y2 = 1;y2 <= m;++y2)
                    ret = (ret + dfs(x1,y1,x2,y2)) % mod;
    return ret;
}
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%s",a[i] + 1);
    for(register int i1 = -1;i1 <= 1;++i1)
        for(register int j1 = -1;j1 <= 1;++j1)
            if(i1 || j1)
                for(register int i2 = -1;i2 <= 1;++i2)
                    for(register int j2 = -1;j2 <= 1;++j2)
                        if(i2 || j2)
                            ans = (ans + ((!i1 || !j1) ? -1LL : 1LL) * ((!i2 || !j2) ? -1LL : 1LL) * calc(i1,j1,i2,j2) + mod) % mod;
    printf("%d\n",ans);
}