md这题打得我手都流汗了

发现这题可以这样建图，对于一条边 $(u,v)$ ，如果 $v$ 是水那么就赋这条边的边权为 $1$，如果不是那么就赋 $0$，并且 $u$，$v$ 都不能是岩石。

题意转为最短路与最短路计数

发现有 $0$ 边就很不好搞，那么就把有 $0$ 边的一些节点合并在一起，直接 dfs 即可

非常奇怪的是我写了个并查集做法，挂了，写了 dfs 做法，又挂了，最后写了大概一两个小时才打出来，写一次挂一次，写到第十次左右的时候才过了样例，心态爆炸了

还有这题样例实在是太...人肉模拟的时候给整吐了

以下是代码：

#include<bits/stdc++.h>
using namespace std;
int a[35][35],dfn[35][35],tot,simati[3535];
int di[8]={-2,-2,-1,-1,1,1,2,2};
int dj[8]={-1,1,-2,2,-2,2,-1,1};
queue<int> q;
int dis[30005],vis[30005];
long long cnt[30005];
vector<int> e[30005];
void spfa(int st){
	memset(dis,0x3f,sizeof(dis));
	q.push(st);dis[st]=0;cnt[st]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=0;i<e[u].size();++i){
			int v=e[u][i];
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;cnt[v]=cnt[u];
				if(!vis[v]) q.push(v),vis[v]=1;
			}
			else if(dis[v]==dis[u]+1) cnt[v]+=cnt[u];
		}
	}
}
int n,m;
int num(int i,int j){
	return (i-1)*m+j;
}
bool check(int i,int j){
	return 1<=i&&i<=n&&1<=j&&j<=m;
}
void dfs(int id,int i,int j){
	if(dfn[i][j]) return;
	dfn[i][j]=1;
	for(int k=0;k<8;++k){
		int ti=i+di[k],tj=j+dj[k];
		if(!check(ti,tj)) continue;
		if(dfn[ti][tj]) continue;
		//cout<<i<<" "<<j<<" "<<ti<<" "<<tj<<endl;
		if(a[ti][tj]==1) dfs(id,ti,tj);
		else if(a[ti][tj]!=2) dfn[ti][tj]=1,e[id].push_back(num(ti,tj));
	}
}
int main(){
	int st,ed;
	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) st=num(i,j);
			if(a[i][j]==4) ed=num(i,j);
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]==3||a[i][j]==0)
				memset(dfn,0,sizeof(dfn)),
				dfs(num(i,j),i,j);
	spfa(st);
	if(dis[ed]!=0x3f3f3f3f) cout<<dis[ed]-1<<endl<<cnt[ed];
	else cout<<-1;
	return 0;
}