最短路【洛谷P1606】 [USACO07FEB]荷叶塘Lilypad Pond

P1606 [USACO07FEB]荷叶塘Lilypad Pond

第一问简单，第二问是最短路计数。

所以难在建边，要区分荷叶和水。

这里的最短路是指在水上放荷叶的数量。

所以我们要找到等价的荷叶，向所能跳到的荷叶连边。

所以对于每一个水，我们找和他们等价的荷叶，再通过这些荷叶建好水到水之间的边，注意把终点看成水就行了。

code:

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#define int long long

using namespace std;

const int wx=3997;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}

	return sum*f;

}

int n,m,num,sx,sy,tx,ty;

int dis[wx*100],ans[wx*100],vis[wx*100],a[wx][wx],flag[wx][wx];

int head[wx*100],lei_zi[wx*100];

int dx[]={0,2,1,-1,-2,-2,-1,1,2};

int dy[]={0,1,2,2,1,-1,-2,-2,-1};

struct e{

	int nxt,to,dis;

}edge[wx*10];

void add(int from,int to,int dis){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	edge[num].dis=dis;

	head[from]=num;

}

queue<int> q;

void SPFA(){

	for(int i=1;i<=n*m;i++)dis[i]=2145415421546LL;

	dis[(sx-1)*m+sy]=0;ans[(sx-1)*m+sy]=1;

	q.push((sx-1)*m+sy); vis[(sx-1)*m+sy]=1;

	while(q.size()){

		int u=q.front(); q.pop(); vis[u]=0;

		for(int i=head[u];i;i=edge[i].nxt){

			int v=edge[i].to;

			if(dis[v]>dis[u]+edge[i].dis){

				dis[v]=dis[u]+edge[i].dis;

				ans[v]=ans[u];

				if(!vis[v]){

					vis[v]=1;q.push(v);

				}

			}

			else if(dis[v]==dis[u]+edge[i].dis){

				ans[v]+=ans[u];

			}

		}

	}

}

void dfs(int uX,int uY,int ux,int uy){

	lei_zi[(ux-1)*m+uy]=1;

	for(int i=1;i<=8;i++){

		int ex=ux+dx[i];

		int ey=uy+dy[i];

		if(lei_zi[(ex-1)*m+ey]||ex<1||ey<1||ex>n||ey>m)continue;

		if(a[ex][ey]==2)continue;

		if(a[ex][ey]==1){

			dfs(uX,uY,ex,ey);

		}

		else{

			lei_zi[(ex-1)*m+ey]=1;

			add((uX-1)*m+uY,(ex-1)*m+ey,1);

		}

	}

}

signed main(){

	n=read();m=read();

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			int x; x=read();

			a[i][j]=x;

			if(x==3)sx=i,sy=j;

			if(x==4)tx=i,ty=j;

		}

	}

	for(int ux=1;ux<=n;ux++){

		for(int uy=1;uy<=m;uy++){

			if(a[ux][uy]==2||a[ux][uy]==4||a[ux][uy]==1)continue;

			memset(lei_zi,0,sizeof lei_zi);

			dfs(ux,uy,ux,uy);

		}

	}

	SPFA();

	if(dis[(tx-1)*m+ty]==2145415421546LL)puts("-1");

	else printf("%lld\n%lld\n",dis[(tx-1)*m+ty]-1,ans[(tx-1)*m+ty]);

	return 0;

}