1161 : ท่อระบายน้ำ (Sewer)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)

เมืองแห่งหนึ่งมีพื้นที่เป็นรูปสี่เหลี่ยมขนาด a แถวคูณ b คอลัมน์และแบ่งเขตเป็นจำนวนเท่ากับ a×b เขต แต่ละเขตจะมีพิกัด (i, j) โดยเขตที่พิกัด (1, 1) จะอยู่ที่มุมซ้ายบนของพื้นที่สี่เหลี่ยม และแต่ละเขตจะมีท่อระบายน้ำเชื่อมต่อกับเขตเพื่อนบ้านหรือไม่ก็ได้ ดังแสดงในรูป (ให้เครื่องหมาย ลูกศร แสดงถึงท่อระบายน้ำที่เชื่อมระหว่างเขต)



กำหนดให้เขตที่พิกัด (1, 1) เป็นจุดเริ่มปล่อยน้ำทิ้ง โดยจะสามารถระบายน้ำทิ้งไปยังท่อระบายน้ำที่เชื่อมอยู่กับเขตนั้นๆ และแต่ละท่อใช้เวลาระบายน้ำทิ้งจากเขตหนึ่งไปยังเขตหนึ่งด้วยเวลาหนึ่งหน่วย น้ำสามารถไหลได้ 4 ทิศทาง คือไหลไปยังเขตทิศเหนือ ไหลลงเขตทิศใต้ ไหลไปเขตทางตะวันออก และ ไหลไปเขตทางตะวันตก โดยเขตรับน้ำจะไม่สามารถระบายน้ำกลับไปยังเขตก่อนหน้าที่ระบายน้ำมาให้

จงเขียนโปรแกรมเพื่อคำนวณหาระยะเวลาที่น้อยที่สุด ที่น้ำทิ้งอย่างน้อย 2 สายจะมาบรรจบกัน พร้อมทั้งบอกพิกัดของเขตที่น้ำทิ้งมาบรรจบกัน (รับประกันว่าข้อมูลนำเข้าทุกชุด จะมีเขตที่น้ำสองสายมาบรรจบกันที่เกิดขึ้นเร็วที่สุด เพียงเขตเดียวเสมอ) โดยจากรูปตัวอย่างข้างบนนี้ น้ำทิ้งจะเริ่มต้นที่ (1, 1) ในช่วงเวลาที่ 1 และเคลื่อนไปสู่ (2, 1) และ (1, 2) ในช่วงเวลาที่ 2 จากนั้นจึงไปสู่ (3, 1) และ (1, 3) ในช่วงเวลาที่ 3 และถึง (3, 2) กับ (2, 3) ในช่วงเวลาที่ 4 และสุดท้ายจึงมาบรรจบกันที่พิกัด (3, 3) ในช่วงเวลาที่ 5 ตามลำดับ

กำหนดให้แต่ละเขตสามารถมีรูปแบบการติดตั้งท่อระบายน้ำได้ทั้งหมด 4 รูปแบบ เมื่อพิจารณาการเชื่อมต่อทางทิศตะวันออกและทิศใต้เท่านั้น ได้แก่ R หมายถึงเขตนั้นมีท่อระบายน้ำเชื่อมกับเขตทิศตะวันออก, D หมายถึงเขตนั้นมีท่อระบายน้ำเชื่อมกับเขตทิศใต้, B หมายถึงเขตนั้นมีท่อระบายน้ำเชื่อมกับทั้งเขตทิศตะวันออกและทิศใต้, และ N หมายถึงเขตนั้นไม่มีท่อระบายน้ำเชื่อมกับเขตทิศตะวันออกและทิศใต้

 

 

 

ข้อมูลนำเข้า

1.       บรรทัดแรกเป็นค่าของตัวแปร a และ b โดยที่ 2 a,b 100

2.      บรรทัดที่สองถึง a + 1 แต่ละบรรทัด มีตัวอักษรทั้งหมด b ตัว คั่นด้วยช่องว่าง แต่ละตัวระบุถึงสถานะการมีท่อระบายน้ำของเขตแต่ละเขตในพิกัด (i, j) โดยเริ่มจากพิกัดที่ (1, 1) ไปเรื่อยๆ ตามลำดับ และ 1 ia และ 1 jb

ข้อมูลส่งออก

1.       บรรทัดแรกเป็นจำนวนเต็ม 1 ตัว แสดงถึงช่วงเวลาที่น้ำทิ้งมาบรรจบกัน

2.       บรรทัดที่สองเป็นจำนวนเต็ม 2 ตัว คั่นด้วยช่องว่าง ซึ่งเป็นพิกัด (i, j) ที่น้ำทิ้งมาบรรจบกัน



ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 7 (NUTOI7)

 


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 4
B R D N
D R B D
R R R D
N N N N
5
3 3
3 4
B B B D
D N R B
R R R N
5
2 4

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

กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 4 สมาชิก (0 บอท)