This repository has been archived by the owner on Apr 22, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1037.html
46 lines (45 loc) · 5.83 KB
/
1037.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
จักรพรรดิ์แคกตัสผู้ชั่วร้ายครอบครองเข่งวิเศษอยู่ และได้ใช้เข่งวิเศษเทน้ำอย่างไม่หมดสิ้นให้ท่วมป่าอาถรรพณ์ ช่างทาสีและสามสหายเม่นน้อย ซึ่งเดินทางอยู่ในป่า จะต้องรีบเดินทางไปยังรังของตัวบีเวอร์เพื่อให้ปลอดภัยจากน้ำที่กำลังจะท่วม<br />
<br />
เราแทนแผนผังของป่าอาถรรพณ์ด้วยเมตริกซ์ขนาด R แถวและ C คอลัมน์ โดยช่องที่ว่างแทนด้วยตัวอักษร ‘.’ ช่องที่ถูกน้ำท่วมแทนด้วยตัวอักษร ‘*’ และช่องที่เป็นหินแทนด้วยตัวอักษร ‘X’ สำหรับช่องที่เป็นรังของบีเวอร์แทนด้วยตัวอักษร ‘D’ และ ช่องที่ช่างทาสีและ hedgehogs อยู่จะแทนด้วยตัวอักษร ‘S’<br />
<br />
ในแต่ละนาทีที่ผ่านไป ช่างทาสีและสามสหายเม่นน้อย สามารถเดินทางไปได้เพียง 1 ช่อง โดยเลือกจากช่องที่อยู่ถัดไปทางด้านบน ล่าง ซ้าย หรือขวาเท่านั้น และทุก ๆ นาทีน้ำที่ถูกเทออกมาจะไหลไปท่วมช่องที่อยู่ใกล้เคียงได้เพิ่มขึ้น 1 ช่องในทุก ๆ ด้าน สำหรับช่องที่เป็นหินนั้น ไม่ว่าน้ำหรือช่างทาสีและสามสหายเม่นน้อยก็จะไม่สามารถผ่านไปได้ และถ้าน้ำท่วมช่องใดแล้ว ช่างทาสีและสามสหายแม่นน้อยก็จะไม่สามารถข้ามหรือเข้าไปในช่องนั้นได้เช่นกัน อย่างไรก็ตามน้ำจะไม่ท่วมรังของบีเวอร์<br />
<br />
ในการเลือกช่องเดินของช่างทาสีและสามสหายเม่นน้อยมีข้อจำกัดอยู่ว่า จะต้องไม่เลือกเดินไปในช่องที่น้ำกำลังจะท่วมเข้ามาในนาทีเดียวกันพอดี<br />
<br />
หน้าที่ของคุณคือเขียนโปรแกรมเพื่อรับอินพุตเป็นแผนผังของป่าอาถรรพณ์ เพื่อคำนวณหาเวลาเป็นนาทีที่น้อยที่สุดที่ช่างทาสีและสามสหายเมนน้อยจะเดินทางไปถึงรังของบีเวอร์อย่างปลอดภัย<br />
<br />
<u><strong>ข้อมูลนำเข้า</strong></u><br />
<strong>บรรทัดแรก</strong>ประกอบด้วยตัวเลขจำนวนเต็มสองจำนวนที่ระบุจำนวนแถว (R) และจำนวนคอลัมน์ (C) ของป่าอาถรรพณ์ โดยที่ทั้ง R และ C จะมีค่าไม่เกิน 50<br />
<strong>ถัดจากบรรทัดแรก จะเป็นอินพุตอีกจำนวน R บรรทัด </strong>แต่ละบรรทัดมี C ตัวอักษร (ของตัวอักษร ‘.’, ‘*’, ‘X’, ‘D’ หรือ ‘S’ ติดกันไปโดยไม่มีช่องว่างคั่น และทั้งป่าอาถรรพณ์จะมี ‘D’ และ ‘S’ ได้เพียงอย่างละหนึ่งตัวอักษรเท่านั้น<br />
<br />
<u><strong>ข้อมูลส่งออก</strong></u><br />
ตัวเลขแสดงเวลาที่สั้นที่สุดที่เป็นไปได้สำหรับช่างทาสีและสามสหายเม่นน้อยใช้ในการเดินทางไปจนถึงรังของบีเวอร์ ถ้าไม่สามารถเดินทางไปถึงได้ ให้พิมพ์คำว่า ‘KAKTUS’ <br />
<br />
<u><strong>Problem Source</strong></u><strong>: Croatian Open Competition in Informatics<br />
Contest 1 – October 28, 2006</strong><br />
<table>
<tr>
<th>ข้อมูลนำเข้า</th>
<th>ข้อมูลส่งออก</th>
</tr>
<tr>
<td>3 3
<br />D.*
<br />...
<br />.S.</td>
<td>3</td>
</tr>
<tr>
<td>3 3
<br />D.*
<br />...
<br />..S</td>
<td>KAKTUS</td>
</tr>
<tr>
<td>3 6
<br />D...*.
<br />.X.X..
<br />....S.</td>
<td>6</td>
</tr></table>