题解 P1606 【[USACO07FEB]白银莲花池Lilypad Pond】

· · 题解

关于spfa，它还没有凉透

拿道题，第一眼你会觉得跑bfs，但很快你发现原有的荷花会让你看起来很烦，尤其第二问的方案数统计需要两遍bfs

然后你就开始考虑联通块，能不嫩把荷花缩成联通块。但很快你发现问题有出在第二问上。例如：

0 0 x 0 0

1 0 0 0 1

0 0 y 0 0

上面的例子，假如从x到y，可以看出在左边和右边的1是两个联通块，但方案数只有在x和y加荷花一种。

然后不小心看一下标签，发现是spfa。

我们可以去避免遇到那些原本存在的荷花，我们就预处理出每个起点以及水位置的花费1个荷叶能到的地方，然后建边跑spfa就可以了

这样可以有效避免有环的情况，上面的例子就直接从x到y，不会重复算情况了

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
#define IN inline
using namespace std;
const int maxn=50;
const int inf=0x7f7f7f;
int dx[8]={2,2,-2,-2,1,-1,1,-1},dy[8]={-1,1,-1,1,2,2,-2,-2};
struct node{
    int to,next;
}a[100010];
int len,head[maxn*maxn],x,y,st,ed;
void adde(int x,int y){a[++len].to=y;a[len].next=head[x];head[x]=len;}
int n,m,mp[maxn][maxn],d[maxn*maxn],p[maxn][maxn];
long long f[maxn*maxn];
bool b[maxn][maxn],vis[maxn*maxn];
IN void dfs(int o,int x,int y){
    b[x][y]=1;
    for(re int k=0;k<8;k++){
        int xx=x+dx[k],yy=y+dy[k];
        if(xx<1 || yy<1 || xx>n || yy>m || b[xx][yy])continue;
        if(mp[xx][yy]==1) dfs(o,xx,yy);
        else b[xx][yy]=1,adde(o,p[xx][yy]);
    }
}
IN void init(){
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++)
            p[i][j]=(i-1)*m+j;
    for(re int i=1;i<=n;i++){ 
        for(re int j=1;j<=m;j++){
            scanf("%d",&mp[i][j]);
            if(mp[i][j]==3) st=p[i][j];
            if(mp[i][j]==4) ed=p[i][j];
        }
    }
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++){
        if(mp[i][j]==0||mp[i][j]==3){
            memset(b,0,sizeof(b));
            dfs(p[i][j],i,j);
        }
    }
}
queue<int> q;
IN void spfa(){
    memset(d,63,sizeof(d));
    d[st]=0,vis[st]=f[st]=1;
    q.push(st);
    while(!q.empty()){
        x=q.front(); q.pop(); vis[x]=0;
        for(re int k=head[x];k;k=a[k].next){
            int v=a[k].to;
            if(d[v]>d[x]+1){
                d[v]=d[x]+1;f[v]=f[x];
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
            else if(d[v]==d[x]+1) f[v]+=f[x];
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    init();spfa();
    if(d[ed]<inf)printf("%d\n%lld\n",d[ed]-1,f[ed]);
    else printf("-1\n");
    return 0;
}