自动搬运

查看原文

来自洛谷，原作者为

	D_14134 AFOing。。。

搬运于2025-08-24 21:27:01，当前版本为作者最后更新于2018-11-09 09:59:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于spfa，它还没有凉透

拿道题，第一眼你会觉得跑bfs，但很快你发现原有的荷花会让你看起来很烦，尤其第二问的方案数统计需要两遍bfs

然后你就开始考虑联通块，能不嫩把荷花缩成联通块。但很快你发现问题有出在第二问上。例如：

0 0 x 0 0

1 0 0 0 1

0 0 y 0 0

上面的例子，假如从x到y，可以看出在左边和右边的1是两个联通块，但方案数只有在x和y加荷花一种。

然后不小心看一下标签，发现是spfa。

我们可以去避免遇到那些原本存在的荷花，我们就预处理出每个起点以及水位置的花费1个荷叶能到的地方，然后建边跑spfa就可以了

这样可以有效避免有环的情况，上面的例子就直接从x到y，不会重复算情况了

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
#define IN inline
using namespace std;
const int maxn=50;
const int inf=0x7f7f7f;
int dx[8]={2,2,-2,-2,1,-1,1,-1},dy[8]={-1,1,-1,1,2,2,-2,-2};
struct node{
	int to,next;
}a[100010];
int len,head[maxn*maxn],x,y,st,ed;
void adde(int x,int y){a[++len].to=y;a[len].next=head[x];head[x]=len;}
int n,m,mp[maxn][maxn],d[maxn*maxn],p[maxn][maxn];
long long f[maxn*maxn];
bool b[maxn][maxn],vis[maxn*maxn];
IN void dfs(int o,int x,int y){
	b[x][y]=1;
	for(re int k=0;k<8;k++){
		int xx=x+dx[k],yy=y+dy[k];
		if(xx<1 || yy<1 || xx>n || yy>m || b[xx][yy])continue;
		if(mp[xx][yy]==1) dfs(o,xx,yy);
		else b[xx][yy]=1,adde(o,p[xx][yy]);
	}
}
IN void init(){
	for(re int i=1;i<=n;i++)
		for(re int j=1;j<=m;j++)
			p[i][j]=(i-1)*m+j;
	for(re int i=1;i<=n;i++){ 
		for(re int j=1;j<=m;j++){
			scanf("%d",&mp[i][j]);
			if(mp[i][j]==3) st=p[i][j];
			if(mp[i][j]==4) ed=p[i][j];
		}
	}
	for(re int i=1;i<=n;i++)
		for(re int j=1;j<=m;j++){
		if(mp[i][j]==0||mp[i][j]==3){
			memset(b,0,sizeof(b));
			dfs(p[i][j],i,j);
		}
	}
}
queue<int> q;
IN void spfa(){
	memset(d,63,sizeof(d));
	d[st]=0,vis[st]=f[st]=1;
	q.push(st);
	while(!q.empty()){
		x=q.front(); q.pop(); vis[x]=0;
		for(re int k=head[x];k;k=a[k].next){
			int v=a[k].to;
			if(d[v]>d[x]+1){
				d[v]=d[x]+1;f[v]=f[x];
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
			else if(d[v]==d[x]+1) f[v]+=f[x];
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	init();spfa();
	if(d[ed]<inf)printf("%d\n%lld\n",d[ed]-1,f[ed]);
	else printf("-1\n");
	return 0;
}