# 洛谷 P1606 [USACO07FEB]荷叶塘Lilypad Pond 题解【最短路计数】【构造】

毒瘤的建图方式……

## 题目描述

FJ has installed a beautiful pond for his cows’ aesthetic enjoyment and exercise.

The rectangular pond has been partitioned into square cells of M rows and N columns (1 ≤ M ≤ 30; 1 ≤ N ≤ 30). Some of the cells have astonishingly sturdy lilypads; others have rocks; the remainder are just beautiful, cool, blue water.

Bessie is practicing her ballet moves by jumping from one lilypad to another and is currently located at one of the lilypads. She wants to travel to another lilypad in the pond by jumping from one lilypad to another.

Surprising only to the uninitiated, Bessie’s jumps between lilypads always appear as a chess-knight’s move: one move in one direction and then two more in the orthogonal direction (or perhaps two in one direction and then one in the orthogonal direction).

Farmer John is observing Bessie’s ballet drill and realizes that sometimes she might not be able to jump to her destination lilypad because intermediary lilypads are missing.

Ever thrifty, he wants to place additional lilypads so she can complete her quest (perhaps quickly, perhaps by using a large number of intermediate lilypads). Of course, lilypads cannot be placed where rocks already intrude on a cell.

Help Farmer John determine the minimum number of additional lilypads he has to place, and in how many ways he can place that minimum number.

## 输入输出格式

0为水，1为莲花，2为岩石，3为贝西所在的起点，4为贝西想去的终点。

## 输入输出样例

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0


2
3


## 说明

【样例说明】

10000 10X00 10X00
30X00 30000 3000X
00200 0X200 00200
0X040 00040 00040

## 题解：

首先，任何一个点可以向8个方向连边。如果那个方向上的数字是$0$，说明那里没有荷叶，要到那里必须放置一片，所以这样的边边权为$1$。同理，如果那个方向上是$1,3$或者是$4$，边权就为$0$；而对$2$的格子就不连边。

这样找到起点到终点的最短路长度，就是最少要增加的荷叶个数，至此第一问解决了。

第二问看上去是第一问的最短路计数。但是交上去WA仔细观察后发现题目要求的是荷叶摆放方案，而不是奶牛路线方案。同时，$0$权边对正常的最短路计数也有影响。我们就考虑把$0$权边给去掉，那么原图就变成了数字为$0$的点之间的图。这样就要把起点和终点也换成$0$，才方便计算。那么怎么去掉呢？

我们发现，指向数字为$1$的点的边边权都为$0$。如果忽略掉$1$这些点，那么所有$1$能一步到达的$0$点，一定可以通过这个$1$达成只添加一片荷叶就能到达的情况。同时我们发现，$1$与$1$之间可以形成连通块，在连通块中任意两点都可以以$0$的代价互相到达。那么根据上面的推导，在整个连通块中的$1$可以一步到达的$0$点，都可以互相通过连通块上的点以$1$的代价互达。这时我们将一个连通块周围所有的点存下来，让它们两两连边。

同时，一个$0$点自身可以到达周围8个方向数字为$0$的点，把这些点也用权值为$1$的点连起来。此时再求起点到终点的最短路以及最短路计数就可以了。

最后要注意，我们把起点和终点都设为$0$，因此终点会被多算一次，最后输出答案时要记得减掉。同时，因为有两种连边渠道，所以可以在空间允许的情况下使用邻接矩阵。

## Code：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using std::priority_queue;
int f[905][905];
{
f[from][to]=v;
}
{
f[from][to]=v;
f[to][from]=v;
}
int a[50][50];
int n,m,s,t;
int pla(int x,int y)
{
return (x-1)*m+y;
}
int dis[999];
long long way[999];
struct statu
{
int n,dis;
statu(int n,int dis)
{
this->n=n;
this->dis=dis;
}
friend bool operator <(statu _a,statu _b)
{
return _a.dis>_b.dis;
}
};
priority_queue<statu> q;
void dijk()
{
memset(dis,0x3f,sizeof(dis));
memset(way,0,sizeof(way));
dis[s]=0;
way[s]=1;
q.push(statu(s,0));
while(!q.empty())
{
statu k=q.top();
q.pop();
for(int i=1;i<=n*m;++i)
{
if(dis[i]>k.dis+f[k.n][i])
{
dis[i]=k.dis+f[k.n][i];
way[i]=way[k.n];
q.push(statu(i,dis[i]));
}
else if(dis[i]==k.dis+f[k.n][i])
way[i]+=way[k.n];
}

}
return;
}
int x[8]={1,2,2,1,-1,-2,-2,-1};
int y[8]={2,1,-1,-2,-2,-1,1,2};
int used[50][50];
int stk[999],top=0;
bool in[999];
void dfs(int X,int Y)
{
used[X][Y]=1;
for(int k=0;k<=7;++k)
if(X+x[k]>0&&X+x[k]<=n&&Y+y[k]>0&&Y+y[k]<=m)
{
int tmp=a[X+x[k]][Y+y[k]];
if(tmp==0&&!in[pla(X+x[k],Y+y[k])])
{
stk[++top]=pla(X+x[k],Y+y[k]);
in[stk[top]]=1;
}
else if(!used[X+x[k]][Y+y[k]]&&tmp==1)//防止多次找同一个连通块
dfs(X+x[k],Y+y[k]);
}
}
int main()
{
int sx,sy,tx,ty;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
if(a[i][j]==3)
{
s=pla(i,j);
sx=i;
sy=j;
}
if(a[i][j]==4)
{
t=pla(i,j);
tx=i;
ty=j;
}
}
memset(f,0x3f,sizeof(f));
a[sx][sy]=0;
a[tx][ty]=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)//在0之间建边
if(!used[i][j]&&a[i][j]!=2&&a[i][j]!=0)
{
top=0;
memset(in,0,sizeof(in));
dfs(i,j);//dfs寻找连通块
for(int i1=1;i1<=top;++i1)//栈内存的是一步能到达的点编号
for(int j1=i1+1;j1<=top;++j1)
}
else if(a[i][j]==0)
for(int k=0;k<=7;++k)
if(i+x[k]>0&&i+x[k]<=n&&j+y[k]>0&&j+y[k]<=m&&a[i+x[k]][j+y[k]]==0)
dijk();
if(dis[t]==0x3f3f3f3f)
{
puts("-1");
return 0;
}
printf("%d\n%lld\n",dis[t]-1,way[t]);
return 0;
}


### 2 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe