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)
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.
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:
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 :
So, I think this solution is wrong. Pardon me if there is any mistake.
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
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?
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.
Yup right, I got it what you are saying if there will be lot of possible paths then dfs will not works here.
https://stackoverflow.com/questions/16506150/longest-path-on-a-grid-without-revisiting-grid-cells
They say it's NP-hard.