题解 P1606 【[USACO07FEB]荷叶塘Lilypad Pond】
顾z
2018-10-14 19:55:22
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
这道题不错啊,表示很考思维.
首先,我们需要知道放多少莲花,如何放.
因此考虑最短路,方案数,我们就考虑最短路计数.(想信大家都会的)
这题的难点在于**如何建边**.
> 因为贝西可以跳任何一个位置,(任何一个有水的位置都可以放莲花)
>
> 所以我们不能单纯地从起点开始向其他点连边,所以我们要从每一个有水的地方开始.
>
> 由于岩石对答案没有贡献,所以不考虑连边.
多次$dfs$对整个图连边.
既然想到这了,你可能会发现,这是一个二维的最短路,记录状态不太好记录.
因此我们给每一个格子编号,像这样.
当然,还有其他编号方法,这样比较简单罢了.
算某一位置$(x,y)$的编号的话,式子为$idx[x][y]=(x-1)\times m+y$
这样建边操作就简单多了.
然后后面只需要敲一个裸的最短路和最短路计数问题就好了.
**输出添加的荷花的最小的数量的时候要$-1$**
这是因为,这个数量实际上是点权,而我们跑最短路用的是边权.
一个点与两条边相连,所以要$-1$。
``代码``
```c++
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#define int long long
#define clear(a,b) memset(a,b,sizeof a)
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,res[35][35],tot,idx[35][35],dis[1008611];
int sx,sy,fx,fy,s,t,head[1008611],to[1008611];
const int ax[]={2,1,-1,-2,2,1,-1,-2};
const int ay[]={1,2,2,1,-1,-2,-2,-1};
bool vis[35][35],inq[1008611];
struct coc{int u,v;}edge[1008611];
inline void add(int x,int y)
{
edge[++tot].u=head[x];
edge[tot].v=y;
head[x]=tot;
}
void dfs(int id,int x,int y)
{
if(vis[x][y])return;
vis[x][y]=true;
for(R int i=0;i<8;i++)
{
R int nx=x+ax[i],ny=y+ay[i];
if(nx<1 || nx>n || ny>m || ny<1 || vis[nx][ny])continue;
//刚开始写成return,尴尬死了 emm
if(res[nx][ny]==1)dfs(id,nx,ny);
else if(res[nx][ny]!=2)
{
vis[nx][ny]=true;
add(id,idx[nx][ny]);
}
}
}
inline void spfa()
{
queue<int>q;
for(R int i=1;i<=n*m;i++)dis[i]=2147483647;dis[s]=0;
inq[s]=true;q.push(s);to[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();inq[u]=false;
for(R int i=head[u];i;i=edge[i].u)
{
if(dis[edge[i].v]>dis[u]+1)
{
dis[edge[i].v]=dis[u]+1;
to[edge[i].v]=to[u];
if(!inq[edge[i].v])
{
q.push(edge[i].v);
inq[edge[i].v]=true;
}
}
else if(dis[edge[i].v]==dis[u]+1)
to[edge[i].v]+=to[u];
}
}
if(dis[t]<2147483647)printf("%lld\n%lld",dis[t]-1,to[t]);
else printf("-1");
}
signed main()
{
in(n),in(m);
for(R int i=1;i<=n;i++)
for(R int j=1;j<=m;j++)
{
in(res[i][j]);
idx[i][j]=(i-1)*m+j;
if(res[i][j]==3)sx=i,sy=j;
if(res[i][j]==4)fx=i,fy=j;
}
for(R int i=1;i<=n;i++)
for(R int j=1;j<=m;j++)
if(!res[i][j] or res[i][j]==3)
clear(vis,0),dfs(idx[i][j],i,j);
s=idx[sx][sy];t=idx[fx][fy];
spfa();
}
```