首页分享【jzoj4855】【荷花池塘】【最短路】

【jzoj4855】【荷花池塘】【最短路】

来源：花匠小妙招时间：2025-01-11 16:56

题目大意

于大夫建造了一个美丽的池塘，用来让自己愉快的玩耍。这个长方形的池子被分割成了M 行和N 列的正方形格子。池塘中有些地方是可以跳上的荷叶，有些地方是不能放置荷叶也不能跳上的岩石，其他地方是池水（当然于大夫也是不能游泳的）。于大夫十分有趣，他在池塘跳跃的方式和象棋中的马一样可以向八个方向走日字形，而且于大夫只能跳上荷叶。于大夫每天从一个给定的有荷叶的地方出发，试图到达另一个给定的有荷叶的地方。但有一天他发现自己无论如何也不能到达目的地了，除非再在水中放置几个荷叶。于大夫想让你告诉他，最少还需放置几片荷叶？在放置荷叶最少的前提下，最少需要几步能到达目的地？

解题思路

直接spfa，添加荷叶个数为第一关键字，走的步数为第二关键字，跑最短路。

code

#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long #define LD double #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a>b)?b:a) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const inf=214748364; int const maxn=100; int n,m,cnt,map[maxn+10][maxn+10],dis1[maxn+10][maxn+10],dis2[maxn+10][maxn+10], inq[maxn+10][maxn+10],q1[maxn*maxn*10+10],q2[maxn*maxn*10+10],x[10],y[10], w[8][2]={{-1,-2},{-2,-1},{1,2},{2,1},{1,-2},{-1,2},{2,-1},{-2,1}}; int main(){ //freopen("sunset.in","r",stdin); //freopen("sunset.out","w",stdout); freopen("lilypad.in","r",stdin); freopen("lilypad.out","w",stdout); scanf("%d%d",&m,&n); fo(i,1,m) fo(j,1,n){ scanf("%d",&map[i][j]); if(map[i][j]>2){ x[++cnt]=i; y[cnt]=j; } } fo(i,1,m)fo(j,1,n)dis1[i][j]=dis2[i][j]=inf; int head=0,tail=0; dis1[x[1]][y[1]]=dis2[x[1]][y[1]]=0; q1[++tail]=x[1];q2[tail]=y[1]; inq[x[1]][y[1]]=1; /*dis1[x[2]][y[2]]=dis2[x[2]][y[2]]=0; q1[++tail]=x[2];q2[tail]=y[2]; inq[x[2]][y[2]]=1;*/ for(;head!=tail;){ head++; fo(i,0,7) if((1<=q1[head]+w[i][0])&&(q1[head]+w[i][0]<=m) &&(1<=q2[head]+w[i][1])&&(q2[head]+w[i][1]<=n) &&(map[q1[head]+w[i][0]][q2[head]+w[i][1]]!=2) &&((dis1[q1[head]][q2[head]]+(map[q1[head]+w[i][0]][q2[head]+w[i][1]]==0)<dis1[q1[head]+w[i][0]][q2[head]+w[i][1]]) ||((dis1[q1[head]][q2[head]]+(map[q1[head]+w[i][0]][q2[head]+w[i][1]]==0)==dis1[q1[head]+w[i][0]][q2[head]+w[i][1]]) &&(dis2[q1[head]][q2[head]]+1<dis2[q1[head]+w[i][0]][q2[head]+w[i][1]])))){ dis1[q1[head]+w[i][0]][q2[head]+w[i][1]]=dis1[q1[head]][q2[head]]+(map[q1[head]+w[i][0]][q2[head]+w[i][1]]==0); dis2[q1[head]+w[i][0]][q2[head]+w[i][1]]=dis2[q1[head]][q2[head]]+1; if(((q1[head]+w[i][0]!=x[2])||(q2[head]+w[i][1]!=y[2]))&&(!inq[q1[head]+w[i][0]][q2[head]+w[i][1]])){ q1[++tail]=q1[head]+w[i][0]; q2[tail]=q2[head]+w[i][1]; } } inq[q1[head]][q2[head]]=0; } if(dis1[x[2]][y[2]]==inf)printf("-1 -1"); else printf("%d %d",dis1[x[2]][y[2]],dis2[x[2]][y[2]]); return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162