[ ลืมรหัสผ่าน | ลงทะเบียนสมาชิกใหม่ ]    
  


1011 : Block Game
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
สถิติโจทย์ข้อนี้ : ใช้เวลาน้อยที่สุด ทั้งหมด

เกมประกอบด้วยบอร์ดและบล็อก กำหนดให้บอร์ดมีขนาดไม่เกิน 5 x 5 และบล็อกมีไม่เกิน 3 ชนิด โดยบล็อกเท่านั้นที่สามารถเคลื่อนย้ายได้ โดยย้ายไปทางด้านซ้ายหรือด้านขวาเท่านั้นหากมีที่ว่าง ส่วนบอร์ดไม่สามารถเคลื่อนย้ายได้ หลังการเคลื่อนย้าย บล็อกใด ๆ ที่ไม่มีบล็อกหรือบอร์ดรองรับจะตกลงไปทับบล็อกหรือบอร์ดที่อยู่ด้านล่าง หากมีกลุ่มของบล็อกชนิดเดียวกันตั้งแต่ 2 บล็อกขึ้นไปอยู่ติดกัน ไม่ว่าจะเป็นในแนวตั้งหรือแนวนอน กลุ่มของบล็อกนั้นจะถูกลบออกไปจากบอร์ด โดยแต่ละบล็อกที่ถูกลบจะได้คะแนน 5 คะแนน และสำหรับแต่ละการเคลื่อนย้ายที่ไม่ถูกต้องจะได้ -5 คะแนน เช่น การย้ายบล็อกไปยังตำแหน่งของบอร์ด การย้ายบล็อกไปยังตำแหน่งที่มีบล็อกอื่นอยู่ การย้ายบล็อกในตำแหน่งที่ไม่มีบล็อก หรือการพยายามย้ายบอร์ด

ตัวอย่าง
กำหนดตำแหน่งและทิศทางการเคลื่อนย้ายบล็อกอยู่ในรูป (แถว, สดมภ์, ทิศทาง) โดยนับตำแหน่งแถวและสดมภ์ของบอร์ดจากบนลงล่าง และจากซ้ายไปขวาเริ่มต้นจากศูนย์ตามลำดับ และใช้อักษร “L” หรือ “R” เพื่อแสดงทิศทางการเคลื่อนย้ายไปทางซ้ายหรือขวาตามลำดับ



พิจารณาภาพ (A) หากมีคำสั่งให้ย้ายบล็อก (1, 3, L), (0, 1, R) ตามลำดับ จะได้ผลลัพธ์ดังภาพ (B) ถึง (G) โดยจะได้คะแนนรวม 20 คะแนน จากการลบบล็อกจำนวน 4 บล็อกออกไปจากบอร์ด อย่างไรก็ตาม พิจารณาจากภาพ (A) หากมีคำสั่งให้ย้ายบล็อก (1, 3, R), (0, 1, R) ตามลำดับ จะได้ผลลัพธ์ดังภาพ (H) ถึง (J) ซึ่งไม่สามารถย้ายบล็อกใดๆ ออกไปจากบอร์ดได้ ในกรณีนี้จะได้คะแนนรวม -5 คะแนน จากการย้ายบล็อก (1, 3, R) ไปในทิศทางไม่ถูกต้อง (ย้ายบล็อกไปตำแหน่งของบอร์ด) และหลังจากย้ายบล็อก (0, 1, R) ไม่มีบล็อกใดถูกลบออกไปจากบอร์ด
ในข้อมูลทดสอบจะไม่มีกรณีเริ่มต้นที่มีบล็อกชนิดเดียวกันติดกัน และในระหว่างการเคลื่อนย้ายบล็อกจะไม่มีกรณีที่มีกลุ่มของบล็อกชนิดเดียวกันติดกันมากกว่าหนึ่งชุดในเวลาเดียวกัน

อย่างไรก็ตามหลังจากลบบล็อกออกจากบอร์ดแล้วอาจมีบล็อกชนิดเดียวกันตกลงมาและทำให้ถูกลบออกต่อไปได้

คำสั่ง จงเขียนโปรแกรมเพื่อรับข้อมูลโครงสร้างบอร์ดและบล็อก และข้อมูลการเคลื่อนย้ายบล็อก จากนั้นคำนวณหาคะแนนของการย้ายบล็อก พร้อมทั้งแสดงโครงสร้างใหม่ของบอร์ดและบล็อก

ข้อมูลนำเข้า
ข้อมูลนำเข้าประกอบด้วย 2 ส่วน ดังนี้

ส่วนที่ 1
บรรทัดแรกมีเลขจำนวนเต็มบวกสองจำนวน แต่ละค่าจะคั่นด้วยช่องว่างหนึ่งช่องบอกขนาดของแถว (m) และ สดมภ์ (n) ของบอร์ดตามลำดับ
บรรทัดต่อมา m บรรทัด แสดงโครงสร้างของบอร์ดและบล็อก โดยใช้เครื่องหมาย “#” แทนบอร์ด “-” แทนพื้นที่ว่าง และอักษรตัวใหญ่แทนชนิดของบล็อก สำหรับแต่ละบรรทัด ระหว่างสดมภ์จะคั่นด้วยช่องว่างหนึ่งช่อง

ส่วนที่ 2
เป็นข้อมูลนำเข้าต่อจากส่วนที่หนึ่ง ดังนี้
บรรทัดแรกมีเลขจำนวนเต็มบวก l (1 <= l <= 20) บอกจำนวนการเคลื่อนย้ายบล็อก
บรรทัดต่อมา l บรรทัด แต่ละบรรทัดเป็นคำสั่งการเคลื่อนย้ายบล็อก ซึ่งประกอบด้วยค่า 3 ค่า แต่ละค่าจะคั่นด้วยช่องว่างหนึ่งช่องดังนี้
ค่าแรกบอกตำแหน่งแถวจากบนลงล่างเริ่มต้นจากศูนย์
ค่าที่สองบอกตำแหน่งสดมภ์จากซ้ายไปขวาเริ่มต้นจากศูนย์
ค่าที่สามบอกทิศทางการเคลื่อนย้าย โดย “L” ไปทางซ้าย และ “R” ไปทางขวา

ข้อมูลส่งออก
ให้แสดงผลลัพธ์ดังนี้ บรรทัดแรกแสดงคะแนนรวมการเคลื่อนย้ายบล็อก บรรทัดต่อมา m บรรทัด แสดงโครงสร้างใหม่ของบอร์ดและบล็อก

ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 3 มหาวิทยาลัยขอนแก่น

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 5
# A - - #
# # - B #
# A B # #
# # # # #
2
1 3 L
0 1 R 		20
# - - - #
# # - - #
# - - # #
# # # # #
5 5
# A – B #
# B - A #
# # - B #
# A B # #
# # # # #
3
0 1 L
0 3 L
0 1 R 		20
# - - - #
# B - - #
# # - A #
# - - # #
# # # # #

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