1106: 最优对称路径(最短路+记忆化搜索)

2017年07月28日 13点热度 0人点赞 0条评论

1106: 最优对称路径


    
    Time
Limit: 1 Sec    
 Memory
Limit: 128 Mb    
 Submitted: 486     Solved: 135    


Description

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

1106: 最优对称路径(最短路+记忆化搜索)

Symmetry Path Example

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

Input

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

Output

对于每组数据,输出合法路径中,数字之和最小的路径条数除以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

//可以重复走同一个格子,最短路+记忆化搜索
//当wa时有时随便造个数据也是好的 
#include
#include
#include
#include
using namespace std;
const int M=1000000009;
int n,a[201][201],dis[201][201],d[201][201],vis[201][201],mi;
int dir[4][2]= {0,1,1,0,-1,0,0,-1};
void spfa()
{
    memset(vis,0,sizeof(vis));
    memset(dis,6,sizeof(dis));
    dis[1][1]=a[1][1];
    vis[1][1]=1;
    queue qx,qy;
    qx.push(1);
    qy.push(1);
    while(qx.size())
    {
        int fx=qx.front(),fy=qy.front();
        qx.pop();
        qy.pop();
        vis[fx][fy]=0;
        int x,y;
        for(int i=0; i<4; ++i)
        {
            x=fx+dir[i][0];
            y=fy+dir[i][1];
            if(x>0&&x<=n&&y>0&&y<=n&&x+y<=n+1&&dis[x][y]>dis[fx][fy]+a[x][y])
            {
                dis[x][y]=dis[fx][fy]+a[x][y];
                if(!vis[x][y])//这个地方要注意
                {
                    qx.push(x);
                    qy.push(y);
                    vis[x][y]=1;
                }
            }
        }
    }
}
int dfs(int x1,int y1)
{
    if(~d[x1][y1]) return d[x1][y1];
    d[x1][y1]=0;
    int x,y;
    for(int i=0; i<4; ++i)
    {
        x=x1+dir[i][0];
        y=y1+dir[i][1];
        if(x>0&&x<=n&&y>0&&y<=n&&x+y<=n+1&&dis[x][y]==dis[x1][y1]+a[x][y])
            d[x1][y1]=(d[x1][y1]+dfs(x,y))%M;
    }
    return d[x1][y1];
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                scanf("%d",*(a+i)+j);
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; i+j<=n; ++j)
                a[i][j]+=a[n+1-j][n+1-i];
        }
        spfa();//求出单源点最短路 
        mi=1e9;
        for(int i=1; i<=n; ++i)
            mi=min(mi,dis[i][n+1-i]);
        memset(d,-1,sizeof(d));
        for(int i=1; i<=n; ++i)
            if(dis[i][n+1-i]==mi) d[i][n+1-i]=1;
            else d[i][n+1-i]=0;
        printf("%dn",dfs(1,1));
    }
    return 0;
}
未经允许不得转载!1106: 最优对称路径(最短路+记忆化搜索)

update

纸上得来终觉浅, 绝知此事须躬行。