Luogu P1606 [USACO07FEB]Lilypad Pond G 题解

Description

题目链接

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

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

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

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

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

Solution

考虑跑最短路。

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

然后跑spfa就好了。

Code

暂无评论

发送评论 编辑评论


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