1037 : Slikar
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

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
3 3 D.* ... .S.	3
3 3 D.* ... ..S	KAKTUS
3 6 D...*. .X.X.. ....S.	6

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้