2

Given a N*M array of 0 and 1. A lake is a set of cells(1) which are horizontally or vertically adjacent. We are going to connect all lakes on map by updating some cell(0) to 1. The task is finding the way that number of updated cells is the smallest in a given time limit.

I found this similar question: What is the minimum cost to connect all the islands? The solution on this topic get some problem:
1) It uses lib (pulp) to solve the task
2) It take time to get output

Is there an optimization solution for this problem

Thank you in advance

Ann
  • 21
  • 3
  • Do you have any limits on the size of the input? – findusl Oct 09 '18 at 08:45
  • The maximum is 15 * 15 – Ann Oct 09 '18 at 09:38
  • this is quite small, I think you should be able to brute force it. For example from the stack overflow question that you referenced, this answer: https://stackoverflow.com/a/30714737/3795043 – findusl Oct 09 '18 at 09:52
  • This is size of the map. With a map 15*15, you can have more than 100 lakes to connect. – Ann Oct 09 '18 at 10:00
  • yes, but the more lakes you have, the less options you have to put connections. Ofc you need some simple optimizations. Don't try to put connections where they don't connect to anything etc. But what I mean by brute force is that you can go by try and error maybe with backtracking and probably find a optimal solution in that time window. But I don't have prove. If I find time I'll try it. – findusl Oct 09 '18 at 10:44
  • Actually, I've tried to put some optimizations in BFS, like: - do not continue if path length > min - only search in range (min height, max height, min width, max width) of other lakes... but the problem was not solved. I'd appreciate it if you could give me some suggestions for optimizations. Thanks, – Ann Oct 09 '18 at 11:10
  • I found the problem interesting and decided to try a backtracking algorithm. It seems like it is still faulty but I am actually supposed to be working and not doing this, so I can't finish it right now and I do not actually have a Java IDE here, online it is very difficult to debug. Thought I just share it with you if you are interested. https://pastebin.com/SWJWjucg – findusl Oct 09 '18 at 14:01
  • I've run your code but it doesn't pass my cases. Looking forward to your updates :) – Ann Oct 09 '18 at 14:52
  • Yeah that one still seemed faulty. I actually have a good feeling about this one, although it is not quite fast enough sometimes. I am sure there are still some tweaks possible. But are the results correct? https://pastebin.com/gpZdP4Uw – findusl Oct 09 '18 at 20:27

2 Answers2

0

I think this is a tricky question but if you really draw it out and look at this matrix as a graph it makes it simpler. Consider each cell as a node and each connection to its top/right/bottom/left to be an edge. Start by connection the edges of the lakes to the nearby vertices. Keep doing the same for each each and only connect two vertices if it doesn't create a cycle. At this stage carry out the same process for the immediate neighbours of the lakes. Keep doing the same and break if its creating cycles. After this you should have a connected tree.

Once you have a connected tree you can find all the articulation point (Cut vertex) of the tree. (A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components)

The number of cut vertex in the tree (excluding the initial lakes) would be the smallest number of cells that you need to change.

You can search there are many efficient ways to find cut vertex of a graph. Finding articulation points takes O(V+E) Preprocessing takes O(V+E) as it somewhat similar to a BFS.

Ravi Chandak
  • 113
  • 1
  • 9
  • Thanks for your answer. Could you explain more about how you create the tree? I'm afraid that it will exceed the time limit to find all trees. – Ann Oct 09 '18 at 09:59
  • Let me clarify. Actually you don't have to find all trees you have to just create one tree. It is basically expanding out from the lake vertices, you can think of it as a BFS algorithm. Worst case assume we have 2 lakes at each corner. In this case you will expand each cell in the Array. Also as we are building a tree each cell will only be expanded once. Storing the tree created in a new AdjList. Total vertices would be N*M and total edges would be 4*N*M Finding all articulation point is proven to be a O(V+E) algorithm. – Ravi Chandak Oct 09 '18 at 10:15
0

Don't know whether you are still interested but I have an idea. What about a min cost flow algorithm.

Assume you have an m*n 2-d input array and i Islands. Create a graph where each position in the 2-d array is a node and has 4 edges to each neighbour. Each edge will be assigned a cost later on. Each edge has minimum capacity 0 and maximum capacity infinit.

Choose a random island to be the source. Create an extra node target and connect it to all other islands except the source with each new edge having maximum and minimum flow capacity 1 and cost 0.

Now assign the old edges costs, so that an edge connecting two island nodes costs nothing, but an edge between and island and a water node or an edge between two water nodes costs 1.

Calculate min cost flow over this graph. The initial graph generating can be done in nm and the min cost flow algorithm in (nm) ^3

findusl
  • 2,454
  • 8
  • 32
  • 51