ในที่สุด คุณก็ได้พบกับอัญมณีแล้ว แต่ทว่า คุณลืมคิดว่า คุณจะออกจากโบราณสถานนี้อย่างไร... ยิ่งไปกว่านั้น เทพเจ้าที่รักษาสถานที่นี้รู้แล้วว่าคุณมาเยือน และกำลังจะถล่มที่นี่ลงช้าๆ...
โชคดีที่มีเครื่องขนย้ายมวลสารพิเศษ ที่จะย้ายคุณออกไปจากโบราณสถานได้
โชคไม่ดีที่เครื่องขนย้ายมวลสารพิเศษนี้ จะทำงานก็ต่อเมื่อคุณแก้ปัญหา “ปริศนา 15” ได้ เท่านั้น
ปริศนา 15 (Fifteen Puzzle) เป็นเกมปริศนาที่มีหมากรูปสี่เหลี่ยมวางอยู่ในตารางกริดขนาด 4×4 หน่วย กำกับหมายเลขตั้งแต่ 1 ถึง 15 ผู้เล่นสามารถเลื่อนหมากแต่ละตัวไปแทนที่ช่องว่างได้ จนกว่ารูปแบบของตัวเลขในกริดจะอยู่ในสถานะสิ้นสุดซึ่งมีตำแหน่งดังนี้
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
กำหนดสถานะเริ่มต้นของเกมปริศนา 15 มาให้ หน้าที่ของคุณคือตอบลำดับการเลื่อนหมากแก้ปริศนานี้ โดยไม่จำเป็นต้องใช้จำนวนครั้งในการเลื่อนน้อยที่สุด (โปรดดูเกณฑ์การให้คะแนนประกอบ)
ลำดับของการเลื่อนหมาก จะถูกกำหนดด้วยสตริงของอักษรสี่ประเภท (N, E, W, S) ซึ่งหมายถึงตำแหน่งของหมากซึ่งจะถูกเลื่อนมาแทนช่องว่าง ณ ขณะนั้น
สมมติสถานะเริ่มต้นของเกมปริศนา 15 ที่กำหนดให้มีลักษณะดังนี้
1 |
2 |
8 |
3 |
5 |
7 |
10 |
4 |
9 |
6 |
11 |
|
13 |
14 |
15 |
12 |
หนึ่งในลำดับการแก้ปริศนานี้ ที่สามารถนำไปสู่สถานะสิ้นสุดของเกมได้ อาจแทนด้วยสตริง SWNNNESWWSESE ยังมีรูปแบบลำดับการแก้ปริศนานี้อีกมากมายที่ให้ผลลัพธ์แบบเดียวกัน
คุณต้องรีบแก้ปริศนานี้โดยด่วน ก่อนที่โบราณสถานจะพังทลาย...
งานของคุณ
จงเขียนโปรแกรมรับสถานะเริ่มต้นของเกมจากข้อมูลนำเข้า คำนวณลำดับการเลื่อนหมากตัวเลขแต่ละตัวซึ่งทำให้เกมอยู่ในสถานะสิ้นสุด แล้วแสดงลำดับการเลื่อนหมากดังกล่าวเป็นสตริงออกทางข้อมูลส่งออก รับประกันว่าปริศนาที่กำหนดมาให้ สามารถแก้หาคำตอบได้เสมอ
การให้คะแนน
เนื่องจากในการแข่งขันจริง มีการให้คะแนนแบบ Partial Score กล่าวคือผู้เข้าแข่งขันอาจได้คะแนนจากผลลัพธ์ที่ถูกต้องน้อยกว่า 100% จากชุดข้อมูลทดสอบหนึ่ง ๆ ได้
โดยผู้เข้าแข่งขันจะได้คะแนนเต็มเมื่อจำนวนครั้งในการเลื่อนหมากน้อยกว่า 5,000 ครั้งเท่านั้น ซึ่งในระบบตรวจของ programming.in.th จะแสดงผลการตรวจเป็น '
P' ส่วนในกรณีที่จำนวนครั้งในการเลื่อนหมากมากกว่า 5,000 ระบบตรวจจะแสดงผลตรวจเป็น '
S' ซึ่งหมายความว่าได้คะแนนบางส่วนสำหรับชุดข้อมูลทดสอบนั้น ๆ
หมายเหตุ ในกรณีที่โปรแกรมให้ผลัพธ์ที่ไม่ถูกต้อง เช่น ไม่สามารถแก้ปัญหาโจทย์ได้ หรือมีตัวอักษรที่ไม่ใช่ N, E, W, S หรือมีการเลื่อนออกนอกกระดาน จะได้ 0 คะแนน (ซึ่งแสดงผลการตรวจเป็น '
-') ทันที
ข้อมูลนำเข้า
มีจำนวนเต็มทั้งสิ้น 4 บรรทัด บรรทัดละ 4 ตัว แทนตัวเลขในสถานะเริ่มต้นของเกมทั้งหมด
จำนวนเต็มบวก 1 ถึง 15 แทนหมายเลขกำกับหมากในตำแหน่งนั้น ๆ
จำนวน 0 จะหมายถึงช่องว่างของตาราง
ข้อมูลส่งออก
มีบรรทัดเดียว แสดงชุดตัวอักษรซึ่งประกอบด้วยอักขระสี่ประเภท (N, E, W, S) ซึ่งบอกลำดับการเลื่อนหมากตัวเลขทั้งหมดเพื่อแก้ปริศนา 15 ที่กำหนดให้
โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา:
TOI.CPP:03-2009 ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
1 2 8 3
5 7 10 4
9 6 11 0
13 14 15 12 | SWNNNESWWSESE |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้