Path题解

退役已久,昨天帮小学弟做题,嗯这题很水,然而我蒟蒻,半年没写代码,写了两小时……

我太了!

题目内容:

题目描述:

​ Euphemia到一个N*N的药草田里采药,她从左上角的格子田(第一行,第一列)出发,要到达右下角(第N行,第N列)的格子田,每次她可以走到与当前格子有边相邻的格子去,但她不会走已经走过的格子,而且出于对美的要求,她走过的路径是关于 左下-右上 对角线对称的。由于地势不同,在每个格子田采药都会有一个疲劳度Tij,Euphemia想知道:有多少条合法路径,可以使得她采药的疲劳度最小。

输入格式:

​ 多组数据。

​ 每组数据第一行一个整数N,接下来N行,每行N个非零数字(1,2,3…9中一个),表示格子田的疲劳度。

​ 当N=0,输入结束。

输出格式:

​ 对于每组数据,输出一个整数表示答案,答案%1000000009。

样例输入:

1
2
3
4
5
6
7
8
2
1 1
1 1
3
1 1 1
1 1 1
2 1 1
0

样例输出:

1
2
2
3

数据范围与限制:

​ 对于20%的数据满足N<=5。

​ 对于另外20%的数据满足N<=40。

​ 对于100%的数据满足N<=100,不超过50组数据。

题解

由于要求路径沿着左下到右上对称,我们可以考虑把这张地图沿着对称轴对折,累加对称的点权值,在剩余的三角图上跑一遍最短路计数。

数据只有100,SPFA死了,但它还活着!直接在网格上SPFA,同时DP维护最短路计数。

最短路计数方法洛谷 P1144 最短路计数

一些细节处理,网格图只要在左上部分的三角范围内跑,判断是否在这个范围可以使用x+y<=n+1来判断。

注意多组数据,每次初始化。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 2019-04-20
// Antares

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

using LL=long long;

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;

//#define FIO //文件读写

const int maxn=110;
const int mod=1e9+9;

int read()
{
int ans=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ans=ans*10+ch-'0',ch=getchar();
return ans*f;
}

const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

int n;
int graph[maxn][maxn];
LL dis[maxn][maxn],dp[maxn][maxn];
bool vis[maxn][maxn];

void init()
{
memset(graph,0x7f,sizeof graph);
memset(dis,0x7f,sizeof dis);
memset(vis,0,sizeof vis);
memset(dp,0,sizeof dp);
}

void SPFA_will_be_alive_forever() //最短路计数
{
using Pair=std::pair<int,int>;
using std::make_pair;
std::queue<Pair> que;

dis[1][1]=graph[1][1];
dp[1][1]=1;
que.push(make_pair(1,1));

while(!que.empty())
{
Pair from=que.front();
que.pop();
int x=from.first,y=from.second;
vis[x][y]=0;

if(x+y>n+1)
continue;

for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if(tx>0 && tx<=n && ty>0 && ty<=n && tx+ty<=n+1)
{
if(dis[tx][ty]>dis[x][y]+graph[tx][ty])
{
dis[tx][ty]=dis[x][y]+graph[tx][ty];
dp[tx][ty]=dp[x][y];
if(tx+ty<n+1 && !vis[tx][ty])
{
que.push(make_pair(tx,ty));
vis[tx][ty]=1;
}
}
else if(dis[tx][ty]==dis[x][y]+graph[tx][ty])
{
if(tx+ty<n+1 && !vis[tx][ty])
{
dp[tx][ty]=0;
que.push(make_pair(tx,ty));
vis[tx][ty]=1;
}
dp[tx][ty]+=dp[x][y];
dp[tx][ty]%=mod;
}
}
}
}
}

int main()
{
#ifdef FIO
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
#endif

while(n=read())
{
init();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i+j<=n+1)
graph[i][j]=read();
else
graph[n-j+1][n-i+1]+=read(); //对折

SPFA_will_be_alive_forever();

LL ans=0,min_cost=linf;
for(int i=1;i<=n;i++)
min_cost=std::min(min_cost,dis[i][n-i+1]);

for(int i=1;i<=n;i++)
if(min_cost==dis[i][n-i+1])
ans+=dp[i][n-i+1],ans%=mod;
printf("%lld\n",ans);
}
return 0;
}

END.