考虑将平方看做组合意义：两个人走地形序列相同的路径的方案数。
对于方向的问题，可以将方向分为四类：左、上、左上；右、上、右上；左、下、左下；右、下、右下。
那么一条路径一定是一直走同类方向的。
然而一直向左、上、右、下的路径会被算重，于是再减去即可。
使用记搜实现（否则较难确定转移顺序）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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);
}