2026 : ปริศนา 15 (fifteen)
Problem type : Batch
Time limit : 0.1 second(s)
Memory limit : 32 megabyte(s)
      ในที่สุด คุณก็ได้พบกับอัญมณีแล้ว แต่ทว่า คุณลืมคิดว่า คุณจะออกจากโบราณสถานนี้อย่างไร... ยิ่งไปกว่านั้น เทพเจ้าที่รักษาสถานที่นี้รู้แล้วว่าคุณมาเยือน และกำลังจะถล่มที่นี่ลงช้าๆ... 

      โชคดีที่มีเครื่องขนย้ายมวลสารพิเศษ ที่จะย้ายคุณออกไปจากโบราณสถานได้
โชคไม่ดีที่เครื่องขนย้ายมวลสารพิเศษนี้ จะทำงานก็ต่อเมื่อคุณแก้ปัญหา “ปริศนา 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

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

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