สามก๊กรวมเป็นหนึ่ง (acm15_three_kingdom)


Time limit:
1000 ms
Memory limit:
32 MB

ในสมัยราชวงศ์ฮั่น แผ่นดินจีนถูกแบ่งออกเป็นสามก๊ก ได้แก่ วุยก๊ก (ปกครองโดยโจโฉ), จ๊กก๊ก (ปกครองโดยเล่าปี่) และ ง่อก๊ก (ปกครองโดยซุนกวน) ภายหลังแผ่นดินจีนทั้งสามก๊กก็ถูกรวมเป็นหนึ่งได้ ในข้อนี้ ก๊กเดียวกันจะติดกันในสี่ทิศทางได้แก่ บน, ล่าง, ซ้าย และ ขวา เท่านั้น

แผ่นดินจีนมีขนาด R แถว C คอลัมน์ โดย . คือ ทะเล และ X (ตัวเอกซ์ใหญ่) คือ แผ่นดิน เช่น R=6, C=14 ดังภาพ

ภาพซ้าย คือ ภาพแผ่นดินจีนเริ่มต้น

ภาพตรงกลาง คือ รายละเอียดก๊กทั้งสามก๊ก

ภาพทางขวา คือ แผ่นดินจีนใหม่ ที่ถมทะเลเพิ่ม 2 ช่อง เพื่อรวมสามก๊กเข้าด้วยกัน

จงเขียนโปรแกรมเพื่อหาจำนวนช่องที่น้อยที่สุดที่ต้องถมทะเลเพื่อรวมสามก๊กเข้าด้วยกัน

Input

บรรทัดแรก รับจำนวนเต็มบวก Q แทนจำนวนคำถาม โดยที่ Q ไม่เกิน 15 ในแต่ละคำถาม

บรรทัดแรก รับจำนวนเต็มบวก R C ตามลำดับห่างกันหนึ่งช่องว่าง โดยที่ R, C ไม่เกิน 50

อีก R บรรทัดต่อมา รับตารางขนาด R x C โดยที่ . คือ ทะเล และ X (เอกซ์ใหญ่) คือ แผ่นดิน

รับประกันว่า ทุกชุดข้อมูลทดสอบจะถูกสร้างมาอย่างดี ให้แผ่นดินจีนมีสามก๊กอย่างถูกต้อง

Output

Q บรรทัด แต่ละบรรทัดให้แสดงจำนวนช่องที่น้อยที่สุดที่ต้องถมทะเลเพื่อรวมสามก๊กเข้าด้วยกันตามลำดับของข้อมูลนำเข้า

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None