→题目链接←
spfa的原理就是不断地找，如果找到更优的更新那个点目前的状态使它变得更优
所以这个题一看就是spfa
就是判断是否有更优时，需要分三个级别，每次更新的东西不一样
比如碰到了添加荷叶一样时，就需要判断是否为最短路，如果路径长度还是一样，就要使路径数量+1
注意:
1、记录方案数的数组一定要用long long
2、inf不要作死开的太小qwq
代码:
#include<iostream> #include<cstdio> #include<queue> #include<vector> #define inf 999999999 #define ll long long using namespace std; struct point{ int x,y; friend bool operator == (point a,point b){ if(a.x==b.x && a.y==b.y)return true; return false; } }; struct node{ point now; int len; int num; }; point s,e; int n,m; int a[33][33]; int dis[33][33]; int add[33][33]; int num[33][33]; int tox[8]={-2,-1,1,2,2,1,-1,-2}; int toy[8]={1,2,2,1,-1,-2,-2,-1}; bool vis[33][33]; queue<point>q; int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ scanf("%d",&a[i][j]); if(a[i][j]==3)s.x=i,s.y=j; if(a[i][j]==4)e.x=i,e.y=j; dis[i][j]=inf; add[i][j]=inf; } } dis[s.x][s.y]=0; point t; t=s; num[s.x][s.y]=1; add[s.x][s.y]=0; vis[s.x][s.y]=true; q.push(t); while(!q.empty()){ t=q.front(); q.pop(); if(t==e){ continue; } for(int i=0; i<8; i++){ point t1=t; t1.x+=tox[i]; t1.y+=toy[i]; if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m)continue; if(a[t1.x][t1.y]==2)continue; int len=0; if(a[t1.x][t1.y]==0)len=1; if(add[t1.x][t1.y]>add[t.x][t.y]+len){ add[t1.x][t1.y]=add[t.x][t.y]+len; dis[t1.x][t1.y]=dis[t.x][t.y]+1; num[t1.x][t1.y]=num[t.x][t.y]; if(!vis[t1.x][t1.y])q.push(t1),vis[t1.x][t1.y]=true; } else if(add[t1.x][t1.y]==add[t.x][t.y]+len){ if(dis[t1.x][t1.y]>dis[t.x][t.y]+1){ dis[t1.x][t1.y]=dis[t.x][t.y]+1; num[t1.x][t1.y]=num[t.x][t.y]; if(!vis[t1.x][t1.y])q.push(t1),vis[t1.x][t1.y]=true; } else if(dis[t1.x][t1.y]==dis[t.x][t.y]+1){ num[t1.x][t1.y]+=num[t.x][t.y]; if(!vis[t1.x][t1.y])q.push(t1),vis[t1.x][t1.y]=true; } } } vis[t.x][t.y]=false; } if(add[e.x][e.y]==inf)printf("-1\n"); else{ printf("%d\n",add[e.x][e.y]); printf("%d\n",dis[e.x][e.y]); printf("%d\n",num[e.x][e.y]); } return 0; }