Luogu P1606 [USACO07FEB]Lilypad Pond G 题解

Description

题目链接

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格（1≤M,N≤30）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。

约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。

请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。

Solution

考虑跑最短路。

由于需要计数，可以把所有可以互相到达荷花之间合并成一个点，这样就不会算重。

然后跑spfa就好了。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
int dx[8]={2,2,-2,-2,1,-1,1,-1},dy[8]={-1,1,-1,1,2,2,-2,-2};
int n,m,a[35][35],vis[35][35],fir[35*35],nxt[35*35*35*35],son[35*35*35*35],tot,dis[35*35],f[35*35],used[35*35],inf,s,t;
inline void add(int x,int y){++tot,nxt[tot]=fir[x],fir[x]=tot,son[tot]=y;}
inline void dfs(int now,int x,int y){
vis[x][y]=1;
for(int i=0;i<8;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
if(vis[xx][yy]) continue ;
if(a[xx][yy]==1) dfs(now,xx,yy);
//荷花缩点
else vis[xx][yy]=1,add(now,(xx-1)*m+yy);
//连边
}
}
}
queue<int> q;
inline void spfa(){
while(!q.empty()) q.pop();
memset(used,0,sizeof(used));
memset(dis,63,sizeof(dis));inf=dis[0];
memset(f,0,sizeof(f));
q.push(s);
used[s]=1;dis[s]=0;f[s]=1;
while(!q.empty()){
int u=q.front();q.pop();used[u]=0;
for(int to,i=fir[u];i;i=nxt[i]){
to=son[i];
if(dis[to]>dis[u]+1){
dis[to]=dis[u]+1;
f[to]=f[u];
if(!used[to]){
used[to]=1;
q.push(to);
}
}else if(dis[to]==dis[u]+1) f[to]+=f[u];
}
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
a[i][j]=read();
if(a[i][j]==3) s=(i-1)*m+j;
if(a[i][j]==4) t=(i-1)*m+j;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==0a[i][j]==3) memset(vis,0,sizeof(vis)),dfs((i-1)*m+j,i,j);
spfa();
if(dis[t]<inf) write(dis[t]-1),putchar('\n'),write(f[t]);
else puts("-1");
}