โปรแกรมหาต้นทุนขั้นต่ำในการรับทองคำในสองตำแหน่งที่กำหนดใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติและค่าอื่นๆ เช่น row, col, erow0, ecol0, erow1 และ ecol1 หากตำแหน่งปัจจุบันของเราคือเมทริกซ์ [row, col] และเราต้องการรับทองคำที่อยู่ที่เมทริกซ์ [erow0, ecol0] และเมทริกซ์ [erow1, ecol1] เราสามารถขึ้น ลง ซ้าย และขวาได้ แต่เมื่อเราอยู่ที่เซลล์ (r, c) เราต้องจ่ายเมทริกซ์ต้นทุน [r, c] แม้ว่าเราจะลงจอดที่เซลล์มากกว่าหนึ่งครั้ง เราก็ไม่ ต้องจ่ายค่าใช้จ่ายสำหรับเซลล์นั้นอีกครั้ง เราต้องหาต้นทุนขั้นต่ำในการรับทองคำทั้งสองแห่ง

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

แถว =0, col =0, erow0 =0, ecol0 =3, erow1 =2, ecol1 =2 แล้วเอาท์พุตจะเป็น 8 ตามที่เราอยู่ (0, 0) และต้องการเลือกทองจากตำแหน่ง (0, 3) และ (2, 2) ดังนั้นก่อนอื่นให้ย้ายจาก (0, 0) เป็น (0, 3) โดยสามขั้นตอนแล้วกลับมาที่ (0,0) จากนั้นไปที่ (2, 2) โดยทำตาม 1 เซลล์ที่ทำเครื่องหมายไว้

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

• กำหนดฟังก์ชัน is_valid() นี่จะใช้เวลา x, y

• คืนค่า จริง เมื่อ x และ y อยู่ในช่วงของเมทริกซ์ มิฉะนั้น จะเป็นเท็จ

• กำหนดฟังก์ชัน min_cost() นี่จะใช้เวลา sx, sy

• heap :=ฮีปที่มีไอเท็ม (เมทริกซ์[sx, sy], sx, sy)

• diss :=เมทริกซ์ที่มีขนาดเท่ากันกับเมทริกซ์ที่กำหนดและเติมด้วย inf

• diss[sx, sy] :=เมทริกซ์[sx, sy]

• ขณะที่ฮีปไม่ว่างให้ทำ

  • (ราคา, x, y) :=องค์ประกอบแรกของฮีปและลบองค์ประกอบแรกออกจากฮีป

  • สำหรับแต่ละคู่ (nx, ny) ใน [(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1) ] ทำ

    • ถ้า is_valid(nx, ny) และ matrix[nx, ny] + cost

      • edge :=matrix[nx, ny]

      • diss[nx, ny] :=edge + cost

      • แทรก (ขอบ + ราคา, nx, ny) ลงในฮีป

• ขากลับ

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• res :=inf

• a :=min_cost(row, col), b :=min_cost(erow0, ecol0), c :=min_cost(erow1, ecol1)

• สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ

  • สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ

    • res :=ขั้นต่ำของ res และ (a[i, j] + b[i, j] + c[i, j] - 2 * matrix[i, j])

• ผลตอบแทน

ตัวอย่าง

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

import heapqimport mathclass Solution:def Solve(ตัวเอง, เมทริกซ์, แถว, col, erow0, ecol0, erow1, ecol1):def is_valid(x, y):return x>=0 and y>=0 and x  
อินพุต
 <ก่อนหน้า>[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]], 0, 0, 0, 3, 2 , 2

ผลลัพธ์

8