[USACO07FEB]Lilypad Pond-蒲公英云

[USACO07FEB]Lilypad Pond

Link

考场上把我送走的一道题

考试时，晃眼一看，这不是裸的最短路计数吗？！赶忙写好了代码，自信地关闭了文件。然后，0分……

那么回过头来，到底错在哪里？只有新加的荷叶才会被统计，而原来就有的荷叶不算在方案数里（学长把题目魔改了，并且说的不是很清楚，一直没搞懂样例，然后我就挂了）

那怎么样才能使得不把原来就有的荷叶作为状态算在方案数里？因为原来有的荷叶直接可以跳，不需要花费，所以不把它与它可以跳到的点连边，而是把它作为中转节点，把它可以到达的所有点互相连边，最后转化为最短路计数。

可是就这样过了吗？并没有，还有一种情况没有考虑。就是两个原本就有的荷叶可以相互到达的情况，此时就相当于有两个中转节点，需要把它们可以到达的至多16个点互相连边（此过程可以用bfs解决）。如果是三个及三个以上呢？以此类推罢了。

Code:

#include<stdio.h> #include<string.h> #include<queue> using namespace std; #define ll long long #define INF 0x3f3f3f3f #define N 100 template<class T> inline void read(T &x){ x=0;char c=getchar();T flag=1; while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();} x*=flag; } struct E{ int next,to; ll dis; }e[(N*N)<<4]; int dx[10]={-2,-2,-1,-1,1,1,2,2}, dy[10]={-1,1,-2,2,-2,2,-1,1}; int n,m,a[N][N],s,t,top,sta[N*N],head[N*N],cnt; bool in[N*N],vis[N*N],mark[N*N][N*N]; ll dis[N*N],ans[N*N]; queue<int> Q; inline bool check(int x,int y){ if(x<1||x>n||y<1||y>m) return 0; if(a[x][y]==2) return 0; return 1; } inline void add(int id,int to,int dis){ e[++cnt]=(E){head[id],to,dis}; head[id]=cnt; } void dfs(int x,int y){ for(int op=0;op<8;op++){ int xx=x+dx[op],yy=y+dy[op]; if(!check(xx,yy)) continue; if(!a[xx][yy]&&!in[(xx-1)*m+yy]){ in[(xx-1)*m+yy]=1; sta[++top]=(xx-1)*m+yy; } if(a[xx][yy]==1&&!vis[(xx-1)*m+yy]){ vis[(xx-1)*m+yy]=1; dfs(xx,yy); } } } void bfs(){ memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); Q.push(s); ans[s]=1,dis[s]=0,vis[s]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(dis[v]==dis[u]+e[i].dis){ ans[v]+=ans[u]; if(!vis[v]&&v!=t){ vis[v]=1; Q.push(v); } } if(dis[v]>dis[u]+e[i].dis){ dis[v]=dis[u]+e[i].dis; ans[v]=ans[u]; if(!vis[v]&&v!=t){ vis[v]=1; Q.push(v); } } } } } int main(){ // freopen("chess.in","r",stdin); // freopen("chess.out","w",stdout); read(n),read(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ read(a[i][j]); if(a[i][j]==3){ s=(i-1)*m+j; a[i][j]=0; } if(a[i][j]==4){ t=(i-1)*m+j; a[i][j]=0; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(a[i][j]) continue; for(int op=0;op<8;op++){ int x=i+dx[op],y=j+dy[op]; if(check(x,y)&&(!a[x][y])) add((i-1)*m+j,(x-1)*m+y,1); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==1&&(!vis[(i-1)*m+j])){ top=0; memset(in,0,sizeof(in)); vis[(i-1)*m+j]=1; dfs(i,j); for(int k=1;k<=top;k++) for(int p=k+1;p<=top;p++) if(!mark[sta[k]][sta[p]]){ mark[sta[k]][sta[p]]=mark[sta[p]][sta[k]]=1; add(sta[k],sta[p],1),add(sta[p],sta[k],1); } } bfs(); if(!ans[t]) printf("-1"); else printf("%lld\n%lld",dis[t]-1,ans[t]); } /* 3 4 3 0 0 0 0 0 1 4 2 2 2 0 */