题目传送门
建图
首先，根据题目，可以判断出这是一道最短路计数问题。
但是要跑最短路，首先要用他给的信息建图，这是非常关键的一步。
根据题意，我们可以想出以下建图规则：
-
起点或是一个空白处可以花费 \(1\) 代价走向其八个方向。
-
若走到了莲叶上，则可以继续向莲叶的八个方向走，并且还是只花费 \(1\) 代价。
-
石头不能被走到。
-
不能有点在以一个固定点出发的路径上被走到两次（不是最优了）。
由于权值（代价）只有 \(1\)，所以不必记录，有边就代表 \(1\) 代价了。
我们可以用 \(\text{dfs}\) 来建图：
void build(int XX,int YY,int x,int y){
if(mark[x][y]) return ;
mark[x][y]=1;
for(int i=0;i<8;i++){
int xx=x+X[i],yy=y+Y[i];
if(xx<1||xx>n||yy<1||yy>m||mark[xx][yy]) continue;
if(a[xx][yy]==1) build(XX,YY,xx,yy);
else if(a[xx][yy]!=2) mark[xx][yy]=1,e[XX][YY].push_back({xx,yy});
}
}
int main(){
......
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=0&&a[i][j]!=3) continue;
for(int o=1;o<=n;o++) for(int p=1;p<=m;p++) mark[o][p]=0;
build(i,j,i,j);
}
}
......
}
需要注意的几个细节：
- 每一个
0或3都应该作为起点去跑一次，并且跑之前要把 \(mark\) 清空。 - 每次 \(\text{dfs}\) 要把起点传入，因为走到莲叶再往外拓展时边还是连到起点上的，并不是连到前一个走到的点上。原因上面已经讲了。（笔者因为这个错误调了好久 qwq）
- 每次搜到一个点或连上一个点都需要将其标记掉，否则路径数可能变多（然而只 WA 了两个点？）
最短路计数
关于SPFA，他还没 s 透！
在部分题中，SPFA 还是很实用的。
建好图，本题就是较常规的最短路计数，按着板子写就好了，没有什么特别的。
初始 \(cnt[sx][sy]=1\)（起点），然后只需要在普通最短路松弛操作后加这行东西就好了：
if(dis[tmp.x][tmp.y]==dis[k.x][k.y]+1){
cnt[tmp.x][tmp.y]+=cnt[k.x][k.y];
}
至于为什么很好理解，不多赘述。
最后统计答案时有一个注意点，就是我们计算的最短路是包括走到终点的一步的，而题目要求的是需要布置莲叶的数量，不包括终点，所以输出第一个数应该是 \(dis[gx][gy]-1\) 。
还有，最短路数量会爆 \(\text{int}\) ，\(cnt\) 数组记得开 \(\text{long long}\) 。
完整代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
int n,m,a[55][55],dis[55][55],sx,sy,gx,gy;
long long cnt[55][55];
int X[8]={1,1,-1,-1,2,2,-2,-2},Y[8]={2,-2,2,-2,1,-1,1,-1};
bool vis[55][55],mark[55][55];
int kkk;
struct node{
int x,y;
};
vector<node> e[55][55];
queue<node> q;
void build(int XX,int YY,int x,int y){
if(mark[x][y]) return ;
mark[x][y]=1;
for(int i=0;i<8;i++){
int xx=x+X[i],yy=y+Y[i];
if(xx<1||xx>n||yy<1||yy>m||mark[xx][yy]) continue;
if(a[xx][yy]==1) build(XX,YY,xx,yy);
else if(a[xx][yy]!=2) mark[xx][yy]=1,e[XX][YY].push_back({xx,yy});
}
}
void spfa(int sx,int sy){
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dis[i][j]=1e9;
dis[sx][sy]=0,vis[sx][sy]=1,cnt[sx][sy]=1;
q.push({sx,sy});
while(q.size()){
node k=q.front();q.pop();
vis[k.x][k.y]=0;
for(int i=0;i<e[k.x][k.y].size();i++){
node tmp=e[k.x][k.y][i];
if(dis[tmp.x][tmp.y]>dis[k.x][k.y]+1){
dis[tmp.x][tmp.y]=dis[k.x][k.y]+1;
if(!vis[tmp.x][tmp.y]){
vis[tmp.x][tmp.y]=1;
q.push(tmp);
}
}
if(dis[tmp.x][tmp.y]==dis[k.x][k.y]+1){
cnt[tmp.x][tmp.y]+=cnt[k.x][k.y];
}
}
}
}
signed main(){
IOS;cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==3) sx=i,sy=j;
if(a[i][j]==4) gx=i,gy=j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=0&&a[i][j]!=3) continue;
for(int o=1;o<=n;o++) for(int p=1;p<=m;p++) mark[o][p]=0;
build(i,j,i,j);
}
}
spfa(sx,sy);
if(dis[gx][gy]!=1e9) cout<<dis[gx][gy]-1<<endl<<cnt[gx][gy];
else cout<<-1;
return 0;
}