题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1031&pid=2
题目由于要找对称的路径，那么狠明显可以把右下角的每一块加到左上角对应的每一块上。然后就变成从左上角走到对角线的最短路径的个数。
先跑一遍最短路径得到p(i, j)从起点到(i, j)的最短路径。
然后就是找最短路径的个数。显然cnt(i, j)是它周围点能通过最短路径到它的cnt的和。这一处可以使用记忆化搜索来完成。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long
#define MOD 1000000009 using namespace std; const int maxN = ;
int xx[] = {-, , , };
int yy[] = { , , -, };
int n, a[maxN][maxN], mi;
int p[maxN][maxN];
int cnt[maxN][maxN];
bool vis[maxN*maxN]; void input()
{
scanf("%d", &n);
for (int i = ; i < n; ++i)
for (int j = ; j < n; ++j)
scanf("%d", &a[i][j]);
for (int i = ; i < n; ++i)
for (int j = ; j < n; ++j)
if (i+j != n-)
a[i][j] += a[n--j][n--i];
memset(p, -, sizeof(p));
memset(vis, false, sizeof(vis));
} void cal()
{
int k, x, y, ix, iy;
queue<int> q;
p[][] = a[][];
q.push();
vis[] = true;
while (!q.empty())
{
k = q.front();
q.pop();
vis[k] = false;
x = k/;
y = k%;
for (int i = ; i < ; ++i)
{
ix = x+xx[i];
iy = y+yy[i];
if (ix+iy > n- || ix < || iy < ) continue;
if (p[ix][iy] == - || p[ix][iy] > p[x][y]+a[ix][iy])
{
p[ix][iy] = p[x][y]+a[ix][iy];
if (!vis[*ix+iy])
{
q.push(*ix+iy);
vis[*ix+iy] = true;
}
}
}
}
mi = p[][n-];
for (int i = ; i < n; ++i)
mi = min(mi, p[i][n--i]);
} int dfs(int x, int y)
{
if (cnt[x][y] != -) return cnt[x][y];
int ix, iy, all = ;
for (int i = ; i < ; ++i)
{
ix = x+xx[i];
iy = y+yy[i];
if (ix+iy > n- || ix < || iy < ) continue;
if (p[ix][iy]+a[x][y] == p[x][y])
all = (all+dfs(ix, iy))%MOD;
}
cnt[x][y] = all;
return all;
} void work()
{
cal();
memset(cnt, -, sizeof(cnt));
cnt[][] = ;
int ans = ;
for (int i = ; i < n; ++i)
if (mi == p[i][n--i])
ans = (ans+dfs(i, n--i))%MOD;
printf("%d\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
input();
work();
}
return ;
}