Link
只有新加的荷叶才会被统计，原来就有的荷叶不算在方案数里
因为原来有的荷叶直接可以跳，不需要花费，所以不把它与它可以跳到的点连边，而是把它作为中转节点，把它可以到达的所有点互相连边，最后转化为最短路计数。
还有一种情况。两个原本就有的荷叶可以相互到达的情况，此时就相当于有两个中转节点，需要把它们可以到达的至多16个点互相连边（用bfs解决）。
Code:
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define N 100
template<class T>
inline void read(T &x){
x=0;char c=getchar();T flag=1;
while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
x*=flag;
}
struct E{
int next,to;
ll dis;
}e[(N*N)<<4];
int dx[10]={-2,-2,-1,-1,1,1,2,2},
dy[10]={-1,1,-2,2,-2,2,-1,1};
int n,m,a[N][N],s,t,top,sta[N*N],head[N*N],cnt;
bool in[N*N],vis[N*N],mark[N*N][N*N];
ll dis[N*N],ans[N*N];
queue<int> Q;
inline bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return 0;
if(a[x][y]==2) return 0;
return 1;
}
inline void add(int id,int to,int dis){
e[++cnt]=(E){head[id],to,dis};
head[id]=cnt;
}
void dfs(int x,int y){
for(int op=0;op<8;op++){
int xx=x+dx[op],yy=y+dy[op];
if(!check(xx,yy)) continue;
if(!a[xx][yy]&&!in[(xx-1)*m+yy]){
in[(xx-1)*m+yy]=1;
sta[++top]=(xx-1)*m+yy;
}
if(a[xx][yy]==1&&!vis[(xx-1)*m+yy]){
vis[(xx-1)*m+yy]=1;
dfs(xx,yy);
}
}
}
void bfs(){
memset(dis,INF,sizeof(dis));
memset(vis,0,sizeof(vis));
Q.push(s);
ans[s]=1,dis[s]=0,vis[s]=1;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]==dis[u]+e[i].dis){
ans[v]+=ans[u];
if(!vis[v]&&v!=t){
vis[v]=1;
Q.push(v);
}
}
if(dis[v]>dis[u]+e[i].dis){
dis[v]=dis[u]+e[i].dis;
ans[v]=ans[u];
if(!vis[v]&&v!=t){
vis[v]=1;
Q.push(v);
}
}
}
}
}
int main(){
// freopen("chess.in","r",stdin);
// freopen("chess.out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
read(a[i][j]);
if(a[i][j]==3){
s=(i-1)*m+j;
a[i][j]=0;
}
if(a[i][j]==4){
t=(i-1)*m+j;
a[i][j]=0;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]) continue;
for(int op=0;op<8;op++){
int x=i+dx[op],y=j+dy[op];
if(check(x,y)&&(!a[x][y]))
add((i-1)*m+j,(x-1)*m+y,1);
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==1&&(!vis[(i-1)*m+j])){
top=0;
memset(in,0,sizeof(in));
vis[(i-1)*m+j]=1;
dfs(i,j);
for(int k=1;k<=top;k++)
for(int p=k+1;p<=top;p++)
if(!mark[sta[k]][sta[p]]){
mark[sta[k]][sta[p]]=mark[sta[p]][sta[k]]=1;
add(sta[k],sta[p],1),add(sta[p],sta[k],1);
}
}
bfs();
if(!ans[t]) printf("-1");
else printf("%lld\n%lld",dis[t]-1,ans[t]);
}
/*
3 4
3 0 0 0
0 0 1 4
2 2 2 0
*/