由题目意思来看，既然是对称的路径，那么我们只需要把左上三角的值与右下三角的值加到左上三角上，然后计算从0,0到对称线上的点计算最短路，这样可以大大减少计算时间。
那么存网格的时候可以用二维数组存放起来，以测试用例存放就是：
2 2 1
2 1 1
2 1 1
然后我们看
第一条，(1,1)—>(1,2)—>(2,2)
第二条，(1,1)—>(2,1)—>(2,2)
第三条，(1,1)—>(1,2)—>(1,3)
这样明显减少了计算量。
在网格中，可以直接用dijkstra算法借助队列（STL中的queue）求出其最短路，这样有了最短路就只差最后一步统计了。
最后一步统计的思想是这样的，首先是搜索方法，对于每个“左下-右上”对称线上的点出发，到（0,0）搜索。
标记一个状态dp[x][y]，代表x，y到0,0上的最短路有dp[x][y]条，且dp[0][0]=1；设tx，ty的集合是{（x-1，y），（x+1，y），（x，y+1），（x，y-1）}，如果0,0到x，y的最短路径等于0,0到tx，ty的最短路径加上 [x][y]这个点网格的值，那么状态转移方程为的dp[x][y]是四个d[tx][ty]之和,当然前提是tx,ty这些点是合理的，没有超过网格界限。
还有一个最重要的剪枝是，当dp[x][y]这个点已经统计过了，那么无需再次统计，用一个flag[x][y]来表示是否是第一次统计，如果是第一次统计的话那么需要计算，如果不是的话直接返回dp[x][y]，因为已经统计好了。
1 #include<iostream>
2 #include<cstdio>
3 #include<memory.h>
4 #include<queue>
5 using namespace std;
6 int map[205][205], dis[205][205],d[205][205], n,mins, dir[4][2] = {-1,0,0,1,1,0,0,-1};
7 bool flag[205][205];
8
9 #define M 1000000009
10 void bfs()
11 {
12 queue<int> q;
13 int i, x, y, x1, y1;
14 x = 1; q.push(x);
15 y = 1; q.push(y);
16 dis[1][1] = map[1][1];
17 while(!q.empty())
18 {
19 x = q.front(); q.pop();
20 y = q.front(); q.pop();
21 for(i = 0; i < 4; ++i)
22 {
23 x1 = x + dir[i][0];
24 y1 = y + dir[i][1];
25 if(map[x1][y1] && dis[x1][y1] > dis[x][y] + map[x1][y1])
26 {
27 dis[x1][y1] = dis[x][y] + map[x1][y1];
28 q.push(x1); q.push(y1);
29 }
30 }
31 }
32 mins = dis[1][n];
33 for(i=2; i<n; ++i)
34 if(dis[i][n-i+1] < mins)
35 mins = dis[i][n-i+1];
36 }
37
38 int dfs(int x,int y)
39 {
40 int i,tx,ty;
41 if(x==1 && y==1) return 1;
42 if(flag[x][y]) return d[x][y];
43 flag[x][y]=true;
44
45 d[x][y]=0;
46 for(i=0;i<4;i++)
47 {
48 tx=x+dir[i][0];
49 ty=y+dir[i][1];
50 if(map[tx][ty] && dis[x][y] == dis[tx][ty] + map[x][y]) //点睛之笔啊！！！
51 d[x][y]=(d[x][y]+dfs(tx,ty)) % M;
52 }
53 return d[x][y];
54 }
55
56
57 int main()
58 {
59 // freopen("in.txt","r",stdin);
60 int i,j;
61 while(scanf("%d",&n)!=EOF)
62 {
63 if(n==0) break;
64 memset(map,0,sizeof(map));
65 for(i=1; i<=n; ++i)
66 for(j=1; j<=n; ++j)
67 {
68 scanf("%d",&map[i][j]);
69 dis[i][j] = M+2;
70 }
71 for(i=1; i<n; ++i)
72 for(j=1; j<=n-i; ++j)
73 {
74 map[i][j] += map[n-j+1][n-i+1];
75 map[n-j+1][n-i+1] = 0;
76 }
77 bfs();
78 memset(flag,false,sizeof(flag));
79 int key=0; //计算相等路有多少条
80 for(i = 1; i <= n; i++)
81 if(mins == dis[i][n-i+1])
82 key=(key+dfs(i,n-i+1)) % M;
83 printf("%d\n",key);
84
85 }
86 return 0;
87 }
2 #include<cstdio>
3 #include<memory.h>
4 #include<queue>
5 using namespace std;
6 int map[205][205], dis[205][205],d[205][205], n,mins, dir[4][2] = {-1,0,0,1,1,0,0,-1};
7 bool flag[205][205];
8
9 #define M 1000000009
10 void bfs()
11 {
12 queue<int> q;
13 int i, x, y, x1, y1;
14 x = 1; q.push(x);
15 y = 1; q.push(y);
16 dis[1][1] = map[1][1];
17 while(!q.empty())
18 {
19 x = q.front(); q.pop();
20 y = q.front(); q.pop();
21 for(i = 0; i < 4; ++i)
22 {
23 x1 = x + dir[i][0];
24 y1 = y + dir[i][1];
25 if(map[x1][y1] && dis[x1][y1] > dis[x][y] + map[x1][y1])
26 {
27 dis[x1][y1] = dis[x][y] + map[x1][y1];
28 q.push(x1); q.push(y1);
29 }
30 }
31 }
32 mins = dis[1][n];
33 for(i=2; i<n; ++i)
34 if(dis[i][n-i+1] < mins)
35 mins = dis[i][n-i+1];
36 }
37
38 int dfs(int x,int y)
39 {
40 int i,tx,ty;
41 if(x==1 && y==1) return 1;
42 if(flag[x][y]) return d[x][y];
43 flag[x][y]=true;
44
45 d[x][y]=0;
46 for(i=0;i<4;i++)
47 {
48 tx=x+dir[i][0];
49 ty=y+dir[i][1];
50 if(map[tx][ty] && dis[x][y] == dis[tx][ty] + map[x][y]) //点睛之笔啊！！！
51 d[x][y]=(d[x][y]+dfs(tx,ty)) % M;
52 }
53 return d[x][y];
54 }
55
56
57 int main()
58 {
59 // freopen("in.txt","r",stdin);
60 int i,j;
61 while(scanf("%d",&n)!=EOF)
62 {
63 if(n==0) break;
64 memset(map,0,sizeof(map));
65 for(i=1; i<=n; ++i)
66 for(j=1; j<=n; ++j)
67 {
68 scanf("%d",&map[i][j]);
69 dis[i][j] = M+2;
70 }
71 for(i=1; i<n; ++i)
72 for(j=1; j<=n-i; ++j)
73 {
74 map[i][j] += map[n-j+1][n-i+1];
75 map[n-j+1][n-i+1] = 0;
76 }
77 bfs();
78 memset(flag,false,sizeof(flag));
79 int key=0; //计算相等路有多少条
80 for(i = 1; i <= n; i++)
81 if(mins == dis[i][n-i+1])
82 key=(key+dfs(i,n-i+1)) % M;
83 printf("%d\n",key);
84
85 }
86 return 0;
87 }
本来想来个广度搜索，然后直接统计最短路径的个数，谁知悲剧啊，开始是MemoryL ，后来是TIMEL，最后参考了别人的代码觉得最后的dp用的很棒哦。。。