เขาวงกต II ใน C++

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

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

เขาวงกตแสดงด้วยอาร์เรย์ 2 มิติหนึ่งชุด ในที่นี้ 1 หมายถึงผนังและ 0 หมายถึงพื้นที่ว่าง พรมแดนของเขาวงกตเป็นกำแพงทั้งหมด พิกัดต้นทางและปลายทางจะแสดงด้วยดัชนีแถวและคอลัมน์

ดังนั้น หากอินพุตเป็นเหมือนเขาวงกตที่แสดงโดยอาร์เรย์ 2 มิติ

ตำแหน่งเริ่มต้นคือ (0, 4) ตำแหน่งปลายทางคือ (4, 4) จากนั้นเอาต์พุตจะเป็น 12 วิธีหนึ่งที่เป็นไปได้คือ:ซ้ายไปล่างไปซ้ายไปลงขวาไปลงขวา (1+1+3+1+2+2+2) =12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนแถว m :=จำนวนคอลัมน์

• ret :=อินฟินิตี้

• กำหนดระยะอาร์เรย์ 2 มิติของลำดับ n x m

• กำหนดหนึ่งคิว q

• แทรก start ลงใน q

• dist[start[0], start[1]] :=0

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • curr :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • x :=curr[0], y :=curr[1]

  • ถ้า x เหมือนกับปลายทาง[0] และ y เหมือนกับปลายทาง[1] ดังนั้น −

    • ret :=ขั้นต่ำของ ret และ dist[x, y]

  • currDist :=dist[x, y]

  • tempDist :=0

  • ผม :=x

  • ในขณะที่ (i + 1

    • (เพิ่ม i ขึ้น 1)

    • (เพิ่ม tempDist ขึ้น 1)

  • ถ้า currDist + tempDist

    • dist[i, y] :=currDist + tempDist

    • แทรก { i, y } ลงใน q

  • ผม :=x

  • tempDist :=0

  • ในขณะที่ (i - 1>=0 และ grid[i - 1, y] เป็นศูนย์) ทำ −

    • (เพิ่ม tempDist ขึ้น 1)

    • (ลดลง 1)

  • ถ้าcurrDist + tempDist *lt; dist[i, y] จากนั้น −

    • dist[i, y] :=currDist + tempDist

    • แทรก { i, y } ลงใน q

  • ผม :=y

  • tempDist :=0

  • ในขณะที่ (i - 1>=0 และ grid[x, i - 1] เป็นศูนย์) ทำ −

    • (ลดลง 1)

    • (เพิ่ม tempDist ขึ้น 1)

  • ถ้า currDist + tempDist

    • dist[x, i] :=currDist + tempDist

    • แทรก { x, i } ลงใน q

  • ผม :=y

  • tempDist :=0

  • ในขณะที่ (i + 1

    • (เพิ่ม i ขึ้น 1)

    • (เพิ่ม tempDist ขึ้น 1)

  • ถ้า currDist + tempDist

    • dist[x, i] :=currDist + tempDist

    • แทรก { x, i } ลงใน q

• return (ถ้า ret เหมือนกับ inf แล้ว -1 มิฉะนั้น ret)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;class Solution {public:int shortestDistance(vector&grid, vector dist(n, เวกเตอร์  q; q.push(เริ่ม); dist[start[0]][start[1]] =0; while(!q.empty()){ vector =0 &&!grid[i - 1][y]){ tempDist++; ฉัน--; } if(currDist + tempDist =0 &&!grid[x][i - 1]){ i--; tempDist++; } if(currDist + tempDist  v ={{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1 ,0,1,1},{0,0,0,0,0}}; เวกเตอร์ 
อินพุต
 <ก่อน>{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1 },{0,0,0,0,0}}, {0,4},{4,4}

ผลลัพธ์

12