- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a 2d matrix and some other values like row, col, erow0, ecol0, erow1, and ecol1. If our current position is matrix [row, col] and we want to pick up gold that is at matrix [erow0, ecol0] and matrix [erow1, ecol1]. We can go up, down, left, and right but when we are at a cell (r, c), we have to pay cost matrix [r, c], although if we land at a cell more than once, we do not need to pay cost for that cell again. We have to find the minimum cost to pick up gold at both locations.

So, if the input is like

1 | 1 | 1 | 1 | 1 |

1 | 10 | 10 | 10 | 10 |

1 | 1 | 1 | 10 | 10 |

row = 0, col = 0, erow0 = 0, ecol0 = 3, erow1 = 2, ecol1 = 2, then the output will be 8, as we are at (0, 0) and want to pick gold from location (0, 3) and (2, 2). So first move from (0, 0) to (0, 3) by three steps then come back to (0,0) then go to (2, 2) by following the 1 marked cells.

To solve this, we will follow these steps −

Define a function is_valid() . This will take x, y

return true when x and y are in range of matrix, otherwise false

Define a function min_cost() . This will take sx, sy

heap := a heap with item (matrix[sx, sy], sx, sy)

dists := a matrix of same size of given matrix and fill with inf

dists[sx, sy] := matrix[sx, sy]

while heap is not empty, do

(cost, x, y) := first element of heap and delete first element from heap

for each pair (nx, ny) in [(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1) ], do

if is_valid(nx, ny) and matrix[nx, ny] + cost < dists[nx, ny] is non-zero, then

edge := matrix[nx, ny]

dists[nx, ny] := edge + cost

insert (edge + cost, nx, ny) into heap

return dists

From the main method do the following −

res := inf

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

for i in range 0 to row count of matrix, do

for j in range 0 to column count of matrix, do

res := minimum of res and (a[i, j] + b[i, j] + c[i, j] - 2 * matrix[i, j])

return res

Let us see the following implementation to get better understanding −

import heapq import math class Solution: def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1): def is_valid(x, y): return x >= 0 and y >= 0 and x < len(matrix) and y < len(matrix[0]) def min_cost(sx, sy): heap = [(matrix[sx][sy], sx, sy)] dists = [[math.inf] * len(matrix[0]) for _ in range(len(matrix))] dists[sx][sy] = matrix[sx][sy] while heap: cost, x, y = heapq.heappop(heap) for nx, ny in [(x, y - 1), (x + 1, y), (x - 1, y), (x, y + 1)]: if is_valid(nx, ny) and matrix[nx][ny] + cost < dists[nx][ny]: edge = matrix[nx][ny] dists[nx][ny] = edge + cost heapq.heappush(heap, (edge + cost, nx, ny)) return dists res = math.inf a, b, c = min_cost(row, col), min_cost(erow0, ecol0), min_cost(erow1, ecol1) for i in range(len(matrix)): for j in range(len(matrix[0])): res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j]) return res ob = Solution() matrix = [ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10] ] row = 0 col = 0 erow0 = 0 ecol0 = 3 erow1 = 2 ecol1 = 2 print(ob.solve(matrix, row, col, erow0, ecol0, erow1, ecol1))

[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10] ], 0, 0, 0, 3, 2, 2

8

- Related Questions & Answers
- Program to find minimum cost to merge stones in Python
- Program to find minimum cost for painting houses in Python
- Program to find minimum cost to connect all points in Python
- Program to find minimum cost to cut a stick in Python
- Program to find minimum cost to hire k workers in Python
- Program to Find Out the Minimum Cost to Purchase All in Python
- Program to find minimum deletion cost to avoid repeating letters in Python
- Program to find cost to reach final index of any of given two lists in Python
- Program to find minimum total cost for equalizing list elements in Python
- Program to check whether we can pick up and drop every passenger in given list in Python
- Program to find minimum cost to reduce a list into one integer in Python
- Program to find minimum cost to paint fences with k different colors in Python
- Program to Find Out the Minimum Cost Possible from Weighted Graph in Python
- How to pick up and hung up calls in android?
- Minimum Cost To Make Two Strings Identical in C++

Advertisements