1106: 最优对称路径
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 371 Solved: 77
[Submit][Status][Web Board]
Description
给
一个n行n列的网格，每个格子里有一个1到9的数字。你需要从左上角走到右下角，其中每一步只能往上、下、左、右四个方向之一走到相邻格子，不能斜着走，
也不能走出网格，但可以重复经过一个格子。为了美观，你经过的路径还必须关于“左下-右上”这条对角线对称。下图是一个6x6网格上的对称路径。
一个n行n列的网格，每个格子里有一个1到9的数字。你需要从左上角走到右下角，其中每一步只能往上、下、左、右四个方向之一走到相邻格子，不能斜着走，
也不能走出网格，但可以重复经过一个格子。为了美观，你经过的路径还必须关于“左下-右上”这条对角线对称。下图是一个6x6网格上的对称路径。
你的任务是统计所有合法路径中，数字之和最小的路径有多少条。
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 这个题不用SPFA的话就不能用vis数组。。因为优先级不能保证是以费用优先。。但是SPFA一个点能够进队列多次,那么就能够得到从(1,1)->(x,y)最小
的花费了。先预处理最小距离,然后记忆化搜索进行计数,就能够得到所有方案数了,很好的一个题目。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <string.h>
using namespace std;
typedef long long LL;
const LL mod = ;
const int INF =;
const int N = ;
int v[N][N],dis[N][N],n;
LL dp[N][N];
bool vis[N][N];
int dir[][] = {{,},{-,},{,},{,-}};
int MIN;
struct Node{
int x,y;
};
void bfs(){
//memset(vis,false,sizeof(vis));
queue<Node> q;
Node s;
s.x = ,s.y = ,dis[][] = v[][];
q.push(s);
while(!q.empty()){
Node now = q.front();
q.pop();
if(now.x+now.y==n+){
MIN = min(dis[now.x][now.y],MIN);
}
// vis[now.x][now.y] = 1;
for(int i=;i<;i++){
Node next;
next.x = now.x+dir[i][];
next.y = now.y+dir[i][];
if(next.x<||next.y<||next.x>n||next.y>n||next.x+next.y>n+/*||vis[next.x][next.y]*/) continue;
if(dis[next.x][next.y]>dis[now.x][now.y]+v[next.x][next.y]){
dis[next.x][next.y]=dis[now.x][now.y]+v[next.x][next.y];
q.push(next);
}
}
}
}
LL dfs(int x,int y){
if(dp[x][y]!=-) return dp[x][y];
if(x+y==n+){
if(dis[x][y]==MIN) dp[x][y]=;
else dp[x][y] = ;
return dp[x][y];
}
dp[x][y] = ;
for(int i=;i<;i++){
int nextx = x+dir[i][];
int nexty = y+dir[i][];
if(nextx<||nexty<||nextx+nexty>n+) continue;
if(dis[x][y]+v[nextx][nexty]==dis[nextx][nexty])
dp[x][y] = (dp[x][y]+dfs(nextx,nexty))%mod;
}
return dp[x][y];
}
int main(){
while(scanf("%d",&n)!=EOF,n){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&v[i][j]);
if(i+j>n+){
v[n+-j][n+-i] += v[i][j];
}
dis[i][j] =INF;
}
}
MIN = INF;
bfs();
memset(dp,-,sizeof(dp));
LL ans = dfs(,);
printf("%lld\n",ans);
}
return ;
}