Calculate Minimum path from a given point (i,j) to point (x,y) in a martix


  • 0
    A

    There is a circuit board and we need to find the minimum distance from a point i,j to point x,y
    so matrix is like below where b are blocks which you cant cross,and you need to find minimum distance path from point a to point x ,you can move in 4 directions ,east ,west,north and south
    o o a o
    o b o b
    0 x 0 b

    Company :Google


  • 0
    Y

    A BFS will do the trick.


  • 0
    A

    but dont you think time complexity will be very high .I tried a DFS with recursion but the time complexity was exponential


  • 0

    @asj177 with BFS complexity is O(E+V), we have mn4 E maximum (in case there are 0 blocks) and m*n vertexes.
    Why is complexity exponential? We can also run two BFS simultaneosuly from both point and the first point they meet ,we stop


  • 0
    A

    @elmirap Ok so the approach which I tried was
    So lets say with point a we move in 4 directions untill we reach point x.I keep a distance variable which will check if distance is minimum ,there can be many paths to reach the destination ,and had to select the minimum path .So wouldn't there be some kind of DP approach .Whats your view on the same ? With BFS would be do similar ?


  • 0

    @asj177 with BFS you find the minimum path without trying all possibilities, as you do with DFS. I don't see any sense to traverse deep in the graph when you need to find minimum distance to the point


  • 0
    A

    @elmirap Ohh I guess right approach didnt clicke me ...if possible can u plz share the algorithm on how I could have solved this problem .I will help to review my mistake


  • 1

    @asj177 maybe later, but try to make BFS yourself and discuss whether it works with you. You can read some articles on the question
    https://leetcode.com/articles/walls-and-gates/
    Here you will find an approach with BFS


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.