gouravkrosx's blog

Longest Path in a Matrix (Adobe Interview Problem)
By gouravkrosx, history, 3 years ago, In English

A matrix of 0’s and 1’s is given, you have to find largest adjacent string of 1’s, you cannot traverse a cell more than once. A pair of 1’s is adjacent if they are in immediate up, down, right or left cells.

Ex:

0 0 0 0 0
0 0 1 0 0 
1 1 1 0 0 
0 0 1 1 0

ans-5
(not 6 as they are not asking size of largest block!) (2,0 -> 2,1 -> 2,2-> 3,2 -> 3,3)

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

connect all the adjacent cells having value 1. like nodes of a graph,

In the formed graph do a depth-first search and find the longest branch in the dfs-tree.

Or find the diameter of that graph.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Correct me if I am wrong but calculating the diameter of the graph would require two times traversal of each node but we have to traverse each node only one time and apart from that if we run the dfs then I think the order of traversal of nodes in the graph would also matter.So I don't think dfs would work.

    For example, let's take the following matrix:

    0000
0110
0110
0111

    If we start our traversal from the node (1,1) then possible paths can be :

    (1,1)->(1,2)->(2,2)->(2,1)->(3,1)->(3,2)->(3,3) Ans : 7

    But if we traverse the matrix like : 

    (1,1)->(2,1)->(3,1)->(3,2)->(2,2)->(1,2) Ans : 6
                       |
                       (3,3)

    So, I think this solution is wrong. Pardon me if there is any mistake.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is simply finding the diameter of each connected component and return the maximum.

Here is the same problem but only difference is that in this there will be only one connected component.

Related Problem

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The related problem has "The labyrinth is designed in such a way that there is exactly one path between any two free blocks.". This is not given here, is it?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Yep. I think the problem here as stated is asking you to find the longest path in a planar graph. Based on a quick google search no algorithm for it is known.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yup right, I got it what you are saying if there will be lot of possible paths then dfs will not works here.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://stackoverflow.com/questions/16506150/longest-path-on-a-grid-without-revisiting-grid-cells

They say it's NP-hard.

→ Reply