1037 : Slikar
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
จักรพรรดิ์แคกตัสผู้ชั่วร้ายครอบครองเข่งวิเศษอยู่ และได้ใช้เข่งวิเศษเทน้ำอย่างไม่หมดสิ้นให้ท่วมป่าอาถรรพณ์ ช่างทาสีและสามสหายเม่นน้อย ซึ่งเดินทางอยู่ในป่า จะต้องรีบเดินทางไปยังรังของตัวบีเวอร์เพื่อให้ปลอดภัยจากน้ำที่กำลังจะท่วม
เราแทนแผนผังของป่าอาถรรพณ์ด้วยเมตริกซ์ขนาด R แถวและ C คอลัมน์ โดยช่องที่ว่างแทนด้วยตัวอักษร ‘.’ ช่องที่ถูกน้ำท่วมแทนด้วยตัวอักษร ‘*’ และช่องที่เป็นหินแทนด้วยตัวอักษร ‘X’ สำหรับช่องที่เป็นรังของบีเวอร์แทนด้วยตัวอักษร ‘D’ และ ช่องที่ช่างทาสีและ hedgehogs อยู่จะแทนด้วยตัวอักษร ‘S’
ในแต่ละนาทีที่ผ่านไป ช่างทาสีและสามสหายเม่นน้อย สามารถเดินทางไปได้เพียง 1 ช่อง โดยเลือกจากช่องที่อยู่ถัดไปทางด้านบน ล่าง ซ้าย หรือขวาเท่านั้น และทุก ๆ นาทีน้ำที่ถูกเทออกมาจะไหลไปท่วมช่องที่อยู่ใกล้เคียงได้เพิ่มขึ้น 1 ช่องในทุก ๆ ด้าน สำหรับช่องที่เป็นหินนั้น ไม่ว่าน้ำหรือช่างทาสีและสามสหายเม่นน้อยก็จะไม่สามารถผ่านไปได้ และถ้าน้ำท่วมช่องใดแล้ว ช่างทาสีและสามสหายแม่นน้อยก็จะไม่สามารถข้ามหรือเข้าไปในช่องนั้นได้เช่นกัน อย่างไรก็ตามน้ำจะไม่ท่วมรังของบีเวอร์
ในการเลือกช่องเดินของช่างทาสีและสามสหายเม่นน้อยมีข้อจำกัดอยู่ว่า จะต้องไม่เลือกเดินไปในช่องที่น้ำกำลังจะท่วมเข้ามาในนาทีเดียวกันพอดี
หน้าที่ของคุณคือเขียนโปรแกรมเพื่อรับอินพุตเป็นแผนผังของป่าอาถรรพณ์ เพื่อคำนวณหาเวลาเป็นนาทีที่น้อยที่สุดที่ช่างทาสีและสามสหายเมนน้อยจะเดินทางไปถึงรังของบีเวอร์อย่างปลอดภัย
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยตัวเลขจำนวนเต็มสองจำนวนที่ระบุจำนวนแถว (R) และจำนวนคอลัมน์ (C) ของป่าอาถรรพณ์ โดยที่ทั้ง R และ C จะมีค่าไม่เกิน 50
ถัดจากบรรทัดแรก จะเป็นอินพุตอีกจำนวน R บรรทัด แต่ละบรรทัดมี C ตัวอักษร (ของตัวอักษร ‘.’, ‘*’, ‘X’, ‘D’ หรือ ‘S’ ติดกันไปโดยไม่มีช่องว่างคั่น และทั้งป่าอาถรรพณ์จะมี ‘D’ และ ‘S’ ได้เพียงอย่างละหนึ่งตัวอักษรเท่านั้น
ข้อมูลส่งออก
ตัวเลขแสดงเวลาที่สั้นที่สุดที่เป็นไปได้สำหรับช่างทาสีและสามสหายเม่นน้อยใช้ในการเดินทางไปจนถึงรังของบีเวอร์ ถ้าไม่สามารถเดินทางไปถึงได้ ให้พิมพ์คำว่า ‘KAKTUS’
Problem Source: Croatian Open Competition in Informatics
Contest 1 – October 28, 2006
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
เราแทนแผนผังของป่าอาถรรพณ์ด้วยเมตริกซ์ขนาด R แถวและ C คอลัมน์ โดยช่องที่ว่างแทนด้วยตัวอักษร ‘.’ ช่องที่ถูกน้ำท่วมแทนด้วยตัวอักษร ‘*’ และช่องที่เป็นหินแทนด้วยตัวอักษร ‘X’ สำหรับช่องที่เป็นรังของบีเวอร์แทนด้วยตัวอักษร ‘D’ และ ช่องที่ช่างทาสีและ hedgehogs อยู่จะแทนด้วยตัวอักษร ‘S’
ในแต่ละนาทีที่ผ่านไป ช่างทาสีและสามสหายเม่นน้อย สามารถเดินทางไปได้เพียง 1 ช่อง โดยเลือกจากช่องที่อยู่ถัดไปทางด้านบน ล่าง ซ้าย หรือขวาเท่านั้น และทุก ๆ นาทีน้ำที่ถูกเทออกมาจะไหลไปท่วมช่องที่อยู่ใกล้เคียงได้เพิ่มขึ้น 1 ช่องในทุก ๆ ด้าน สำหรับช่องที่เป็นหินนั้น ไม่ว่าน้ำหรือช่างทาสีและสามสหายเม่นน้อยก็จะไม่สามารถผ่านไปได้ และถ้าน้ำท่วมช่องใดแล้ว ช่างทาสีและสามสหายแม่นน้อยก็จะไม่สามารถข้ามหรือเข้าไปในช่องนั้นได้เช่นกัน อย่างไรก็ตามน้ำจะไม่ท่วมรังของบีเวอร์
ในการเลือกช่องเดินของช่างทาสีและสามสหายเม่นน้อยมีข้อจำกัดอยู่ว่า จะต้องไม่เลือกเดินไปในช่องที่น้ำกำลังจะท่วมเข้ามาในนาทีเดียวกันพอดี
หน้าที่ของคุณคือเขียนโปรแกรมเพื่อรับอินพุตเป็นแผนผังของป่าอาถรรพณ์ เพื่อคำนวณหาเวลาเป็นนาทีที่น้อยที่สุดที่ช่างทาสีและสามสหายเมนน้อยจะเดินทางไปถึงรังของบีเวอร์อย่างปลอดภัย
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยตัวเลขจำนวนเต็มสองจำนวนที่ระบุจำนวนแถว (R) และจำนวนคอลัมน์ (C) ของป่าอาถรรพณ์ โดยที่ทั้ง R และ C จะมีค่าไม่เกิน 50
ถัดจากบรรทัดแรก จะเป็นอินพุตอีกจำนวน R บรรทัด แต่ละบรรทัดมี C ตัวอักษร (ของตัวอักษร ‘.’, ‘*’, ‘X’, ‘D’ หรือ ‘S’ ติดกันไปโดยไม่มีช่องว่างคั่น และทั้งป่าอาถรรพณ์จะมี ‘D’ และ ‘S’ ได้เพียงอย่างละหนึ่งตัวอักษรเท่านั้น
ข้อมูลส่งออก
ตัวเลขแสดงเวลาที่สั้นที่สุดที่เป็นไปได้สำหรับช่างทาสีและสามสหายเม่นน้อยใช้ในการเดินทางไปจนถึงรังของบีเวอร์ ถ้าไม่สามารถเดินทางไปถึงได้ ให้พิมพ์คำว่า ‘KAKTUS’
Problem Source: Croatian Open Competition in Informatics
Contest 1 – October 28, 2006
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 3 3 D.* ... .S. | 3 |
| 3 3 D.* ... ..S | KAKTUS |
| 3 6 D...*. .X.X.. ....S. | 6 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 3 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)