题解 P2411 【白银莲花池 】
Creeper_LKF
2017-09-23 16:08:25
优先队列优化+常数优化,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;
}
```