题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23587
题意：给一个n * n的矩阵，每个方格中有一个数字，从左上角走到右下角，且路径必须关于副对角线对称，求使路线上数字和最小的方案数
思路：既然要关于副对角线对称，那么可以把关于副对角线对称的方格的值加到一起去，这样就可以求从起点到副对角线上的点的最短路，展开的话就是从左上角到右下角对称的最短路，遍历副对角线的点找到最短路，再遍历一遍加上所有等于最短路的方案数。此题还可以用递推做
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 10010;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000009;
int n;
int arr[110][110];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int cnt, head[N];
int dis[N], num[N];
bool vis[N];
struct node
{
int to, cost, next;
} g[N*100];
void add_edge(int v, int u, int cost)
{
g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
}
void spfa(int s)
{
queue que;
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
memset(num, 0, sizeof num);
que.push(s);
dis[s] = 0;
num[s] = 1;
vis[s] = true;
while(! que.empty())
{
int v = que.front();
que.pop();
vis[v] = false;
for(int i = head[v]; i != -1; i = g[i].next)
{
int u = g[i].to;
if(dis[u] > dis[v] + g[i].cost) //更新最短路时，要把方案数也更新
{
dis[u] = dis[v] + g[i].cost;
num[u] = num[v];
if(! vis[u])
vis[u] = true, que.push(u);
}
else if(dis[u] == dis[v] + g[i].cost) //跟目前最短路径相等时，把方案数累加
num[u] = (num[u] + num[v]) % MOD;
}
}
}
void solve()
{
cnt = 0;
memset(head, -1, sizeof head);
for(int i = 0; i = 0 && ny >= 0 && nx + ny = 0) //求最小的代价
{
tmp = min(tmp, dis[i*n+j]);
i++, j--;
}
i = 0, j = n - 1;
while(j >= 0) //累加最小代价的方案数
{
if(dis[i*n+j] == tmp)
ans = (ans + num[i*n+j]) % MOD;
i++, j--;
}
printf("%dn", ans);
}
int main()
{
while(scanf("%d", &n), n)
{
for(int i = 0; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
