题解 P2411 【白银莲花池 】

优先队列优化+常数优化，0ms 首先我们看到这道题肯定是bfs，然后众所周知，搜索的复杂度是O(玄学)的（虽然此题数据比较水）。 然后考虑在bfs外的附加任务（以下简称增加莲花数为莲花数）： 使增加莲花数最少；在此前提下路径最短；等路径等莲花数的方案数。 然而本蒟蒻被long long坑了：方案数贼大...... 接下来是具体实现方案。 可以想到，我们平时裸bfs的队列里面的关键字（路径长度）会随着bfs而递增，所以我们一旦达到终点就可以终止bfs，然而这里我们有两个关键字，其中第一关键字是莲花数，第二关键字是路径长度。这说明我们的路径内第一关键字的递增特性被破坏，所有说我们需要调整一下队列来bfs。于是我们想：那岂不是直接按第一关键字排序不久行了？是的，就是这样。 然后于是第一任务与第二任务完成了，考虑第三任务：方案数。 考虑从[i1,j1]和[i2,j2]都可以跳到[i0,j0]（假设[i2,j2]先访问到了[i0,j0]）。现在假设[i0,j0]会是最终解的路径上的一个点。显然这里产生了两种方案到达[i0,j0]，而到达[i1,j1]或[i2,j2]不一定只有一种方式，于是我们将这两种方式相加......且慢！如果这两种方式有可能会有不是最终路径呢？那么如果[i1,j1]不是最终的解，也就是说从该点产生的到终点的路径不符合任务一或任务二，而我们发现[i0,j0]是原解上的路径，这说明什么？说明[i1,j1]->[i0,j0]不在解的路径上，所以[i1,j1]的莲花数或者是步数无法转移到[i0,j0]上来，也就是说step[1]+1!=step[0]（step[1]为步数[i1,j1]的简写）或lily[1]+(是否需要莲花)!=lily[0]（莲花数简写）。所以这就可以判断[i1,j1]的方案是否可以转移到[i0,j0]上。如果[i0,j0]都到不了呢？那么就会有两种情况筛掉：1.像[i1,j1]一样筛掉，2.最终无法成为到达终点的最优解而不会加入到答案中。 所以代码如下： ```cpp #include<cstdio> #include<cctype> #include<queue> #define MAXN 31 #define MAXC 100000 using namespace std; inline int min(int a,int b){//最小值优化（此程序中没用） int c=(b-a)>>31; return (a&c)||(b&~c); } inline char get_char(){//快读 static char buf[10000001],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int num=0; char c; while(isspace(c=get_char())); while(num=num*10+c-48,isdigit(c=get_char())); return num; } int m,n; int matrix[MAXN][MAXN],step[MAXN][MAXN],adds[MAXN][MAXN];/原图，步数，增加莲花数 long long ans[MAXN][MAXN];//方案数 bool vis[MAXN][MAXN];//访问标记 struct P{ int x,y,step,adds; }; struct cmp{ inline bool operator () (P x,P y){ if(x.adds==y.adds) return x.step>y.step;//关键此排序 return x.adds>y.adds; } }; int main(){ m=read(),n=read(); int sx,sy,tx,ty; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ int &p=matrix[i][j]; p=read(); if(p==2) vis[i][j]=true;//可以在下面减去对岩石的判断 if(p==3) sx=i,sy=j; if(p==4) tx=i,ty=j; } } priority_queue<P,vector<P>,cmp> mession;//优先队列优化，把增加莲花最小的放在队首 int d[8][2]={{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}}; // if(sx>tx) d={{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}};//本来想写搜索方向优化，然而又懒得写了 // else d={{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1}}; mession.push((P){sx,sy,0,0}); vis[sx][sy]=true,ans[sx][sy]=1; P u; int temx,temy; while(!mession.empty()){ u=mession.top(),mession.pop(); if(u.x==tx&&u.y==ty){//直接输出 printf("%d\n",u.adds); printf("%d\n",u.step); break; } for(int i=0;i<8;i++){ temx=u.x+d[i][0],temy=u.y+d[i][1]; if(temx<1||temx>m||temy<1||temy>n) continue; bool &p1=vis[temx][temy];//避免反复寻址 int &p2=matrix[temx][temy],&p3=step[temx][temy],&p4=adds[temx][temy],tem1=u.adds; if(p1){ if(step[u.x][u.y]+1==p3&&adds[u.x][u.y]+(!p2)==p4) ans[temx][temy]+=ans[u.x][u.y]; continue;//两种情况：1.目标点没入队是岩石：直接continue，2.目标点已经出队了：那么step和adds一定更新不了答案，3.目标点在队中：不用再入队了 } tem1+=(!p2),p1=true,p3=u.step+1,p4=tem1,ans[temx][temy]=ans[u.x][u.y]; mession.push((P){temx,temy,u.step+1,tem1}); } } if(u.x!=tx||u.y!=ty){//误解 printf("-1"); return 0; } printf("%lld",ans[u.x][u.y]); return 0; } ```