想吃冰卻又敏感保護不足?直擊★美車模手癢不小心...法人:14檔今年本業虧定了晚會結束續攤大腸花 學...
2013-06-04 08:57:45 人氣(153) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][最短路] 12295 - Optimal Symmetric Paths

0
收藏
0
推薦


  Optimal Symmetric Paths 

You have a grid of n rows and n columns. Each of the unit squares contains a non-zero digit. You walk from the top-left square to the bottom-right square. Each step, you can move left, right, up or down to the adjacent square (you cannot move diagonally), but you cannot visit a square more than once. There is another interesting rule: your path must be symmetric about the line connecting the bottom-left square and top-right square. Below is a symmetric path in a 6 x 6 grid.

epsfbox{p12295.eps}

Your task is to find out, among all valid paths, how many of them have the minimal sum of digits?

Input 

There will be at most 25 test cases. Each test case begins with an integer n ( 2$ le$n$ le$100). Each of the next n lines contains n non-zero digits (i.e. one of 1, 2, 3, ..., 9). These n2 integers are the digits in the grid. The input is terminated by a test case with n = 0, you should not process it.

Output 

For each test case, print the number of optimal symmetric paths, modulo 1,000,000,009.

Sample Input 

2
1 1
1 1
3
1 1 1
1 1 1
2 1 1
0

Sample Output 

2
3



The Seventh Hunan Collegiate Programming Contest
Problemsetter: Rujia Liu, Special Thanks: Yiming Li & Jane Alam Jan

把這個正方形對折,然後取最短路到對角線即可。

//對折的地方手殘打錯,一直掛 WA


#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define mod 1000000009
using namespace std;
int n, g[105][105];
int dp[105][105], cnt[105][105], path[105][105];
int inq[105][105];
int dfs(int x, int y) {
    int &v = path[x][y];
    if(inq[x][y])  return v;
    inq[x][y] = 1;
    if(x+1 < n && dp[x][y] == dp[x+1][y]+g[x][y])
        v += dfs(x+1, y);
    if(v >= mod)    v -= mod;
    if(x-1 >= 0 && dp[x][y] == dp[x-1][y]+g[x][y])
        v += dfs(x-1, y);
    if(v >= mod)    v -= mod;
    if(y+1 < n && dp[x][y] == dp[x][y+1]+g[x][y])
        v += dfs(x, y+1);
    if(v >= mod)    v -= mod;
    if(y-1 >= 0 && dp[x][y] == dp[x][y-1]+g[x][y])
        v += dfs(x, y-1);
    if(v >= mod)    v -= mod;
    return v;
}
int main() {
    int i, j, k;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        for(i = 0; i < n; i++)
            for(j = 0; i+j+1 < n; j++)
                g[i][j] += g[n-j-1][n-i-1];
        memset(dp, 63, sizeof(dp));
        memset(cnt, 0, sizeof(cnt));
        memset(inq, 0, sizeof(inq));
        memset(path, 0, sizeof(path));
        dp[0][0] = g[0][0], cnt[0][0] = 1;
        path[0][0] = 1;
        queue<int> X, Y;
        int x, y, tx, ty;
        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        X.push(0), Y.push(0);
        while(!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            inq[x][y] = 0;
            if(x + y == n-1)    continue;
            for(i = 0; i < 4; i++) {
                tx = x+dx[i], ty = y+dy[i];
                if(tx < 0 || ty < 0 || tx >= n || ty >= n)  continue;
                if(dp[tx][ty] > dp[x][y] + g[tx][ty]) {
                    dp[tx][ty] = dp[x][y] + g[tx][ty];
                    if(inq[tx][ty] == 0) {
                        inq[tx][ty] = 1;
                        X.push(tx), Y.push(ty);
                    }
                }
            }
        }
        int mn = 0xfffffff, ret = 0;
        for(i = 0; i < n; i++)
            mn = min(mn, dp[i][n-i-1]);
        memset(inq, 0, sizeof(inq));
        inq[0][0] = 1;
        for(i = 0; i < n; i++) {
            if(dp[i][n-i-1] == mn) {
                ret += dfs(i, n-i-1);
                if(ret >= mod)
                    ret -= mod;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

12295Optimal Symmetric Paths
台長:Morris
人氣(153) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dp、大數] 10328 - Coin Toss
此分類上一篇:[UVA] 391 - Mark-up

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文