ได้รับเมทริกซ์ 2D แทนต้นทุนแต่ละเซลล์ เริ่มจาก (row, col) ต้องไปเก็บทองที่ (erow0, ecol0) และ (erow1, ecol1) เดินได้ 4 ทิศทาง ต้องจ่ายค่าต้นทุนของเซลล์ที่ผ่าน (จ่ายครั้งเดียวต่อเซลล์) หาต้นทุนรวมขั้นต่ำ
ตัวอย่าง
1 1 1 1 1 1 10 10 10 10 1 1 1 10 10
Start: (0,0), Gold: (0,3) และ (2,2) → Output: 8
เส้นทาง: (0,0)→(0,3) กลับ (0,0) แล้วไป (2,2) ผ่านเซลล์ค่า 1
แนวทางแก้ปัญหา
ใช้ Dijkstra 3 ครั้ง จากจุดเริ่มต้น จุดทอง 1 จุดทอง 2 หาระยะทางสั้นที่สุดไปทุกเซลล์ แล้วหาจุดพบกันที่เหมาะที่สุด:
- รัน Dijkstra จากจุดเริ่ม → ได้
dist_start[i][j] - รัน Dijkstra จากทองที่ 1 → ได้
dist_gold1[i][j] - รัน Dijkstra จากทองที่ 2 → ได้
dist_gold2[i][j] - หา
min(dist_start[i][j] + dist_gold1[i][j] + dist_gold2[i][j] - 2×cost[i][j])ทุกเซลล์
ลบ 2×cost เพราะจุดพบนับซ้ำ 3 ครั้งแต่จ่ายจริงแค่ 1 ครั้ง
การใช้งาน (Python)
import heapq
import math
class Solution:
def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
R, C = len(matrix), len(matrix[0])
def dijkstra(sx, sy):
dist = [[math.inf] * C for _ in range(R)]
dist[sx][sy] = matrix[sx][sy]
heap = [(matrix[sx][sy], sx, sy)]
while heap:
cost, x, y = heapq.heappop(heap)
if cost > dist[x][y]:
continue
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < R and 0 <= ny < C:
nc = cost + matrix[nx][ny]
if nc < dist[nx][ny]:
dist[nx][ny] = nc
heapq.heappush(heap, (nc, nx, ny))
return dist
a = dijkstra(row, col)
b = dijkstra(erow0, ecol0)
c = dijkstra(erow1, ecol1)
res = math.inf
for i in range(R):
for j in range(C):
total = a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j]
res = min(res, total)
return int(res)
# ทดสอบ
ob = Solution()
matrix = [[1,1,1,1,1], [1,10,10,10,10], [1,1,1,10,10]]
print(ob.solve(matrix, 0, 0, 0, 3, 2, 2)) # Output: 8
ความซับซ้อน
- Time Complexity: O(R × C × log(R×C))
- Space Complexity: O(R × C)
