You are given a character matrix where each cell can contain one of the following characters:
U: You can move up from this cell with zero cost. Moving in any other direction from this cell incurs a cost of 1. R: You can move right from this cell with zero cost. Moving in any other direction from this cell incurs a cost of 1. L: You can move left from this cell with zero cost. Moving in any other direction from this cell incurs a cost of 1. D: You can move down from this cell with zero cost. Moving in any other direction from this cell incurs a cost of 1.
You need to determine the minimum cost to travel from a starting coordinate (x, y) to a target coordinate (a, b) within the matrix. You are not allowed to move outside the boundaries of the matrix.
Input A character matrix grid of size m x n. Starting coordinates (x, y). Target coordinates (a, b). Output An integer representing the minimum cost to travel from (x, y) to (a, b). Input: grid = [ ['R', 'R', 'D'], ['L', 'D', 'D'], ['U', 'U', 'R'] ] x = 0, y = 0 a = 2, b = 2
Output: 0 Explanation In the given example:
Start at (0, 0) with 'R', move to (0, 1) with zero cost. From (0, 1), move to (0, 2) with zero cost (again 'R'). From (0, 2), move down to (1, 2) with zero cost (cell is 'D'). Finally, from (1, 2), move to (2, 2) with zero cost (cell is 'D'). The total cost is 0, as each move is in the optimal direction with zero cost.
Constraints The dimensions of the matrix m and n will be between 1 and 1000. The starting and target coordinates will always be within the matrix boundaries. I thought of using bfs and saving minimum cost but wasn't able to implement my logic properly can someone help me please
We could connect each cell to four other adjacent cells, and give weights to the edges .
Weight=1, if cost is 1, else weight =0. Now apply dijkstra algorithm from start node to target node and find the minimum distance between them.
This would be our minimum cost.
Time complexity of dijkstra is O(V+ElogV) , which will be 4*n*n*(log(n^2)) = 4*1e6*20. This might pass.
Alternatively, since the edge weight are just 0 and 1, we can also use 0-1 bfs in O(V+E) time. For better implementation , we can first hash all the {i,j} cells using a map , and use integer labels for each cell instead of pair {i,j}.
Inspired by your solution, another way to do this without using Dijkstra, is:
Group all the cells reachable from each cell using 0 cost moves into a single node (DFS or BFS or sth). After performing this grouping for all nodes, we will get a graph where all nodes are connected with the same weight (1) edge. So we can just find shortest path in this graph using BFS and output the number of edges in the path.
Is this a correct solution?
Edit: You second solution seems way better. I didnt read it sorry.
Your approach is probably correct and can be implemented using DSU easily !