SPOJ: BITMAP

Have a look at the problem statement first, http://www.spoj.com/problems/BITMAP/

Today, I solved a very interesting problem on SPOJ. In the initial stages I used Brute Force; judging from the complexity of the algorithm I knew it wouldn’t pass. I searched for some hints on Google. And after that I came up with a very elegant solution.

Anyway, here’s the straightforward problem description: You are given a 2 dimensional array of 0's and 1's. All you have to do is find the distance of each 0 from it’s nearest 1 and write it in its position. It’s given that you can find the distance between any two cells using the formula d= |i1 — i2 | + | j1 — j2 | where i1,j1 and i2, j2 are co-ordinates of the two cells respectively.

So, if the input is:

1
3 4
0001
0011
0110

The output should be:

3 2 1 0
2 1 0 0
1 0 0 1

Brute Force Approach:

1. The 2-D array is a[m][n], say.
2. Store the co-ordinates of all the 1's in a list, say L.
3. for each i,j in a[ ][ ]:
   { dist= INF for each x,y in L: { dist= min(dist,|i-x|+|j-y|) } a[i][j]= dist
   }
4. Print a[ ][ ].

Complexity: O(m^2 * n^2) in the worst case when all the cells are filled with 1's. In the given problem, 1 <= m <=182 and 1<= n <=182. So, obviously, our solution would exceed the Time Limit which is 4 sec.

Optimized Approach:

In this approach we would use Breadth First Search(BFS) Technique on the 2-D array given ( mathematically, it is a graph. A graph is nothing but a connection( called edges) between some points called vertices and in the 2-D array, every cell is assumed to be connected to every cell to it’s left, right, up and down). For unweighted graph, BFS always gives the shortest path between any two nodes. As a matter of fact, Dijkstra’s algorithm is a rip-off of BFS for weighted graph.

Now, here’s the approach, First store the co-ordinates of all the 1's in the 2-D array into a list (say L) and mark all the 1's as INFINITY and all the 0's as -INFINITY in the original array itself. [We don’t need the 0's and 1's anymore. We have all the information we need.] Then, for each element in the list L, call the BFS() method.

Here’s how a typical BFS() works, start from the root, visit it, remove it from queue and add all it’s neighbours to a queue. Then visit each element of the queue in FIFO fashion, (removing them one by one in the process) and keep adding their neighbours to the queue. Do it until the queue is empty which would mean that all elements have been visited. Note that, each element is added and deleted at most once in the queue. Hence, BFS() operation takes linear time (depends only on the number of vertices and edges).

Our BFS() is very similar except one change, we add a neighbor( up, down, left or right) of a node into the queue only when value(current node) +1 < value( neighbor). What is the value() thingy here, you might ask? Good question! In the BFS(), we start traversing from a root-node (which is the cell that contained 1 in the original array) and assign it a value of 0. [ We need to find the nearest distance of all 0's to 1's, remember? So, nearest neighbor containing 1 from a cell (containing 1) is itself, hence its value is assigned 0]. Now, we need to add elements to the queue, right? Look to the left, right, up, down and add that node (or cell, whatever) to the queue only if value(current node) +1 < value( neighbor). Keep doing this, until the queue is empty, which means that all the cells that could’ve been updated by starting from root has been updated.

We call our modified BFS() for every cell in our list L (containing co-ordinates of 1's).

Here’s the code:

Play with it! ☺