Luogu P1606 [USACO07FEB]Lilypad Pond G 题解

Description

题目链接

为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格(1≤M,N≤30)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。

贝西的舞步很像象棋中的马步:每次总是先横向移动一格,再纵向移动两格,或先纵向移动两格,再横向移动一格。最多时,贝西会有八个移动方向可供选择。

约翰一直在观看贝西的芭蕾练习,发现她有时候不能跳到终点,因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然,莲花不能放在石头上。

请帮助约翰确定必须要添加的莲花的最少数量,以及有多少种放置这些莲花的方法。

Solution

考虑跑最短路。

由于需要计数,可以把所有可以互相到达荷花之间合并成一个点,这样就不会算重。

然后跑spfa就好了。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int dx[8]={2,2,-2,-2,1,-1,1,-1},dy[8]={-1,1,-1,1,2,2,-2,-2};
int n,m,a[35][35],vis[35][35],fir[35*35],nxt[35*35*35*35],son[35*35*35*35],tot,dis[35*35],f[35*35],used[35*35],inf,s,t;
inline void add(int x,int y){++tot,nxt[tot]=fir[x],fir[x]=tot,son[tot]=y;}
inline void dfs(int now,int x,int y){
	vis[x][y]=1;
	for(int i=0;i<8;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
			if(vis[xx][yy]) continue ;
			if(a[xx][yy]==1) dfs(now,xx,yy);
//荷花缩点
			else vis[xx][yy]=1,add(now,(xx-1)*m+yy);
//连边
		}
	}
}
queue<int> q;
inline void spfa(){
	while(!q.empty()) q.pop();
	memset(used,0,sizeof(used));
	memset(dis,63,sizeof(dis));inf=dis[0];
	memset(f,0,sizeof(f));
	q.push(s);
	used[s]=1;dis[s]=0;f[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();used[u]=0;
		for(int to,i=fir[u];i;i=nxt[i]){
			to=son[i];
			if(dis[to]>dis[u]+1){
				dis[to]=dis[u]+1;
				f[to]=f[u];
				if(!used[to]){
					used[to]=1;
					q.push(to);
				}
			}else if(dis[to]==dis[u]+1) f[to]+=f[u];
		}
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			a[i][j]=read();
			if(a[i][j]==3) s=(i-1)*m+j;
			if(a[i][j]==4) t=(i-1)*m+j;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==0||a[i][j]==3) memset(vis,0,sizeof(vis)),dfs((i-1)*m+j,i,j);
	spfa();
	if(dis[t]<inf) write(dis[t]-1),putchar('\n'),write(f[t]);
	else puts("-1");
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇