荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 与上次A题异曲同工的一题
发信站: 荔园晨风BBS站 (Sun Apr 18 16:03:15 2004), 站内信件
那总叫什么方法，我都很难形容，总之比较高效
Overfencing
Kolstad and Schrijvers
Farmer John went crazy and created a huge maze of fences out in a field.
Happily, he left out two fence segments on the edges, and thus
created two "exits" for the maze. Even more happily, the maze he created
by this overfencing experience is a `perfect' maze: you can find a
way out of the maze from any point inside it.
Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the
height of the maze; 2*H+1 lines with width 2*W+1 characters that
represent the maze in a format like that shown later - then calculate
the number of steps required to exit the maze from the `worst' point
in the maze (the point that is `farther' from either exit even when
walking optimally to the closest exit). Of course, cows walk only
parallel or perpendicular to the x-y axes; they do not walk on a
diagonal. Each move to a new square counts as a single unit of
distance (including the move "out" of the maze.
Here's what one particular W=5, H=3 maze looks like:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
Fenceposts appear only in odd numbered rows and and odd numbered columns
(as in the example). The format should be obvious and self explanatory.
Each maze has exactly two blank walls on the outside for exiting.
PROGRAM NAME: maze1
INPUT FORMAT
Line 1: W and H, space separated
Lines 2 through 2*H+2: 2*W+1 characters that represent the maze
SAMPLE INPUT (file maze1.in)
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
OUTPUT FORMAT
A single integer on a single output line. The integer specifies the
minimal number of steps that guarantee a cow can exit the maze from
any possible point inside the maze.
SAMPLE OUTPUT (file maze1.out)
9
--
Long long ago,there is a hero stand at the edge of the land,a sword in
hand.......
︵～` ╭) ▁▁
︸ヾ) (╯ ▕天外▏
ゞ7( ︵ )) ▕飞仙▏
╰ ︶へ︶╯ ▔▔
ヅ╯ ジ〉
※ 修改:·kaman 於 Apr 18 16:04:17 修改本文·[FROM: 192.168.111.200]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店