นักล่าขุมทรัพย์นามว่า “อินเดียนา เจ” พลาดพลั้งตกลงไปในหลุมพรางที่ส่งเขาไปอยู่ในเขาวงกตซึ่งมีทางออกอยู่เพียงตำแหน่งเดียวเท่านั้น  เคราะห์ดีที่นายอินเดียนามีแผนที่เขาวงกตติดตัวมาด้วย ทำให้เขาทราบตำแหน่งปัจจุบันของเขาและตำแหน่งของทางออก  จากแผนที่ อินเดียนาพบว่าพื้นที่เขาวงกตถูกแบ่งออกเป็นช่องจำนวน M แถว N หลัก โดยแต่ละช่องในแผนที่จะมีเลขหนึ่งหรือเลขศูนย์อย่างใดอย่างหนึ่ง ซึ่งเลขศูนย์แทนกำแพงและเลขหนึ่งแทนทางเดิน นอกจากนี้เขาวงกตยังวางตัวในทิศเหนือ-ใต้ ตะวันออก-ตะวันตกพอดี
ดังแสดงในภาพตัวอย่างที่อยู่หน้าถัดไป

อย่าง ไรก็ตามปัญหาหนักใจมีอยู่ว่า บริเวณที่อินเดียนาตกลงมาไม่ได้เชื่อมต่อกับทางออก อินเดียนาจึงจำเป็นที่จะต้องระเบิดกำแพงเขาวงกตด้วยระเบิดที่มีติดตัวอยู่ เพียงลูกเดียวเท่านั้น นอกจากนี้อินเดียนาทราบว่าระเบิดนี้มีพลังทำลายกำแพงเขาวงกตได้เพียงหนึ่ง ช่องเท่านั้น

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

ยกตัวอย่างจากแผนที่ในหน้าถัดไป เขาวงกตนี้ประกอบด้วยช่องจำนวนทั้งหมด 5 แถวและ 8 หลัก กำหนดให้อินเดียนาเริ่มต้นในช่องที่ถูกเน้นด้วยวงรี และทางออกอยู่ ณ ตำแหน่งที่เน้นด้วยสามเหลี่ยม หากอินเดียนาระเบิดกำแพงที่ช่องใดช่องหนึ่งที่ถูกเน้นด้วยลูกศรก็จะสามารถ เดินไปถึงทางออกได้  การระเบิดกำแพงที่ช่องอื่น ๆ นอกจากหนึ่งในสี่ช่องนี้ จะไม่ทำให้อินเดียนาไปถึงทางออกได้

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

          จง เขียนโปรแกรมที่มีประสิทธิภาพในการหาจำนวนช่องของกำแพงที่อินเดียนาสามารถทำ การระเบิดเพื่อนำอินเดียนาไปสู่ทางออกได้ รวมทั้งหาระยะทางเดินที่สั้นที่สุดจากจุดเริ่มต้นไปจนถึงทางออก

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

1.       บรรทัดแรกระบุค่า M และ N ซึ่งแทนจำนวนแถวและจำนวนหลักของเขาวงกตตามลำดับ
โดยที่ 1 < M,N < 150 โดย M และ N ถูกคั่นด้วยช่องว่าง

2.       บรรทัดที่สองระบุแถว r_s และหลัก c_s ของช่องที่อินเดียนาเริ่มต้น โดยที่ 1<   r_s < M และ 1 < c_s < N โดย  r_s และ c_s ถูกคั่นด้วยช่องว่าง

3.       บรรทัดที่สามระบุแถว r_e และหลัก c_e ของช่องที่อินเดียนาเริ่มต้น โดยที่ 1<   r_e < M และ 1 < c_e < N โดย  r_e และ c_e ถูกคั่นด้วยช่องว่าง

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

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

1.       บรรทัดแรกระบุจำนวนช่องกำแพงที่อินเดียนาสามารถวางระเบิดและพาอินเดียนาไปถึงทางออกได้