最优对称路径

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
#define LL __int64
#define N 1005
#define MOD 1000000009
const int INF = 0x7f7f7f7f;
struct Node {
    int x, y;
};
LL sum[N][N], dp[N][N], mapp[N][N];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int n;
void bfs() {
    queue<Node> q;
    Node a;
    a.x = 0,a.y = 0;
    q.push(a);
    sum[0][0]=mapp[0][0];
    while(!q.empty())
    {
        Node b = q.front(); q.pop();
        for(int i = 0 ; i < 4 ; i++){
            a.x = b.x+dir[i][0],a.y = b.y+dir[i][1];
            if(a.x<0||a.x>=n||a.y<0||a.y>=n||a.x+a.y>n-1) continue;
            LL cnt = sum[b.x][b.y]+mapp[a.x][a.y];
            if(cnt<sum[a.x][a.y]){
                sum[a.x][a.y] = cnt;
                q.push(a);
            }
        }
    }
}
LL dfs(int x,int y)
{
    LL ans = 0;
        if(x==0&&y==0) return 1;
        if(dp[x][y]) return dp[x][y];
        for(int i = 0 ; i < 4 ; i++){
            int xx = x+dir[i][0],yy = y+dir[i][1];
            if(xx<0||xx>=n||yy<0||yy>=n||xx+yy>n-1) continue;
            if(sum[xx][yy]+mapp[x][y] == sum[x][y])
                ans += dfs(xx,yy)%MOD;
        }
        dp[x][y] = ans;
        return ans%MOD;
}
int main()
{
    while(scanf("%d", &n) != EOF) {
        if(!n) break;
        memset(mapp,0,sizeof(mapp));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                scanf("%I64d", &mapp[i][j]);
                sum[i][j] = INF;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i + j == n - 1) break;
                mapp[i][j] += mapp[n-1-j][n-1-i];
            }
        }
        bfs();
        LL minn = INF;
        for(int i = 0 ; i < n ; i++)
            if(sum[i][n-1-i]<minn) minn = sum[i][n-1-i];
        LL coun = 0;
        memset(dp,0,sizeof(dp));
        for(int i = 0; i < n; i++) {
            if(sum[i][n-1-i] == minn)
               coun =(coun+dfs(i,n-1-i))%MOD;
        }
        printf("%I64d
", coun);
    }
    return 0;
}

View Code

Time Limit:1000MS Memory Limit:65535KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

给一个n行n列的网格，每个格子里有一个1到9的数字。你需要从左上角走到右下角，其中每一步只能往上、下、左、右四个方向之一走到相邻格子，不能斜着走，也不能走出网格，但可以重复经过一个格子。为了美观，你经过的路径还必须关于“左下-右上”这条对角线对称。下图是一个6x6网格上的对称路径。

你的任务是统计所有合法路径中，数字之和最小的路径有多少条。

Input

输入最多包含25组测试数据。每组数据第一行为一个整数n（2<=n<=100）。以下n行每行包含n个1到9的数字，表示输入网格。输入结束标志为n=0。

Output

对于每组数据，输出合法路径中，数字之和最小的路径条数除以1,000,000,009的余数。

Sample Input

Sample Output

2 
3