เส้นทางต้นทุนขั้นต่ำที่อนุญาตให้ย้ายซ้าย ขวา ล่าง และขึ้นใน C++

สมมติว่าเรามีอาร์เรย์ 2 มิติ โดยที่แต่ละเซลล์ประกอบด้วยค่าตัวเลขซึ่งแสดงถึงค่าใช้จ่ายในการเข้าชมผ่านเซลล์นั้น เราต้องหาเส้นทางจากเซลล์ด้านซ้ายบนไปยังเซลล์ด้านขวาล่างโดยที่ค่าใช้จ่ายทั้งหมดที่ใช้ไปนั้นน้อยที่สุด

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 340 เป็น (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340

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

• กำหนดเซลล์ด้วยค่าพิกัด x, y และระยะทาง
• กำหนดเมทริกซ์อาร์เรย์ที่มีขนาด:row x col.
• เติมเมทริกซ์ด้วย inf
• กำหนดขนาดอาร์เรย์ dx:4 :={ - 1, 0, 1, 0}
• กำหนดขนาดอาร์เรย์:4 :={0, 1, 0, - 1}
• กำหนดเซลล์หนึ่งชุดที่เรียกว่า st
• แทรกเซลล์(0, 0, 0) ลงใน st
• เมทริกซ์[0, 0] :=grid[0, 0]
• ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ให้ทำ −
  • k :=องค์ประกอบแรกของ st
  • ลบองค์ประกอบแรกของ st ออกจาก st
  • สำหรับการเริ่มต้น i :=0, เมื่อ i <4, อัปเดต (เพิ่ม i ขึ้น 1), ทำ −
    • x :=k.x + dx[i]
    • y :=k.y + dy[i]
    • ถ้าไม่ใช่ isOk(x, y) แล้ว −
      • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
    • ถ้า matrix[x, y]> matrix[k.x, k.y] + grid[x, y] แล้ว −
      • ถ้าเมทริกซ์[x, y] ไม่เท่ากับ inf แล้ว −
        • ค้นหาและลบเซลล์(x, y, matrix[x, y]) จาก st
      • เมทริกซ์[x, y] :=เมทริกซ์[k.x, k.y] + กริด[x, y]
      • แทรกเซลล์(x, y, เมทริกซ์[x, y]) ลงใน st
• return matrix[แถว - 1, col - 1]

ตัวอย่าง

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

#include ใช้เนมสเปซ std;#define ROW 5#define COL 5class เซลล์ { สาธารณะ:int x, y; ระยะทางภายใน; เซลล์ (int x, int y, ระยะทาง int) :x (x), y (y), ระยะทาง (ระยะทาง) {}};ตัวดำเนินการบูล <(เซลล์ const &a, เซลล์ const &b) { if (a.distance ==b.distance) { ถ้า (a.x !=b.x) ส่งคืน (a.x =0 &&i =0 &&j  st; st.insert(เซลล์(0, 0, 0)); เมทริกซ์[0][0] =ตาราง[0][0]; ในขณะที่ (!st.empty()) { เซลล์ k =*st.begin(); st.erase(st.begin()); สำหรับ (int i =0; i <4; i++) { int x =k.x + dx[i]; int y =k.y + dy[i]; ถ้า (!isOk(x, y)) ดำเนินการต่อ; if (เมทริกซ์[x][y]> matrix[k.x][k.y] + ตาราง[x][y]){ if (เมทริกซ์[x][y] !=INT_MAX) st.erase(st.find(cell( x, y, เมทริกซ์[x][y])))); เมทริกซ์[x][y] =เมทริกซ์[k.x][k.y] + ตาราง[x][y]; st.insert(เซลล์(x, y, เมทริกซ์[x][y])); } } } return matrix[row - 1][col - 1];}int main() { int grid[ROW][COL] ={ 32, 101, 66, 13, 19, 11, 14, 48, 158, 7, 101, 114, 175, 12, 34, 89, 126, 42, 21, 141, 100, 33, 112, 42, 21 }; ศาล <<แก้ (ตาราง ROW, COL);}

อินพุต

ผลลัพธ์:

340