0

It's a variation of the famous problem of Number of Islands. I want to know the algorithm thinking approach(hint). If I want to connect all the islands given that island can be connected in all 8 directions not in only 4 directions. Then how should I approach this problem?

Example

Given

[[1 1 0 0 0]
 [0 1 0 0 1]
 [1 0 0 1 1]
 [0 0 0 0 0]
 [1 0 1 0 1]]

the expected output is 2:

[[1 1 0 0 0]
 [0 1 0 0 1]
 [1 0 0 1 1]
 [0 2 0 2 0]
 [1 0 1 0 1]]

as image

norok2
  • 25,683
  • 4
  • 73
  • 99
Sajan Kumar
  • 65
  • 9
  • 2
    What have you tried so far? – norok2 Mar 30 '21 at 17:03
  • I tried finding the shortest route between every area but I found this solution incorrect while cross-checking. And after that, I couldn't think of anything else. – Sajan Kumar Mar 31 '21 at 17:20
  • I would use a search-tree algorithm. You need to have an heuristic for what is considered a good "move" (e.g. it reduces the number of islands). So, I'd say you first need some code to detect an islands and count the number of islands. It could be cool to parametrize such function(s) with the structure connection matrix (i.e. `[[1, 1, 1], [1, 1, 1], [1, 1, 1]]` in your case). – norok2 Apr 01 '21 at 07:35
  • @norok2 I have adjusted the size of the image. Counting the number of islands,s not a problem. If required I can add code for detecting islands. But can you explain how the search-tree algorithm will be able to solve this problem. I didn't understand how it can solve the above problem. Can you elaborate on that, please? – Sajan Kumar Apr 01 '21 at 08:42
  • You try putting bridges and see if/by how much it improves the situation. – norok2 Apr 01 '21 at 08:54

0 Answers0