Bitmap problem performance boost

Question

Problem statement:

Input is a rectangular bitmap like this:

0001
0011
0110

The task is to find for each black (0) "pixel", the distance to the closest white (1) "pixel". So, the output to the above should be:

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

Below is a working, heavily-commented 78-lines solution. It is very naive, though. How can I make it faster? I know I can search for ones in rectangles centered at a given zero, but I am not sure I need it that complex. I just want to run it under 4s with 200*200 input on Pentium III.

#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;
typedef unsigned short T;
//Maximum size of the array
const size_t MAX = 200;
//Converts string to unsigned integer
T atou(char* s) {
 T x = 0;
 while(*s) x = x*10 + *(s++) - '0';
 return x;
}
//Calculates absolute value
T abs(int a) {
 if(a >= 0) return a;
 else return -a;
}
int main() {
 T testCases, n, m, i, j, min, curDist;
 T A[MAX][MAX];
 char row[MAX];
 //Storing coordinates (i,j) of ones and zeroes from the input matrix
 //hopefully saves a bit of time searching for closest ones
 vector< pair<T,T> > cOnes;
 vector< pair<T,T> > cZeroes;
 pair<T,T> nextPair;
 scanf("%hu",&testCases);
 while(testCases--) {
 //Input matrix is n X m
 scanf("%hu",&n);
 scanf("%hu",&m);
 //Starting from i=1, j=1 for clarity: dealing with i-th row, j-th column
 for(i = 1; i <= n; i++) {
 scanf("%s",row);
 for(j = 1; j <= m; j++) {
 //But then have to subtract one when dealing with char[]
 A[i][j] = atou(&row[j-1]);
 if(row[j-1] == '1') {
 cOnes.push_back(pair<T,T>(i,j));
 //Clearing the array for the next test case
 A[i][j] = 0;
 }
 else cZeroes.push_back(pair<T,T>(i,j));
 }
 }
 //For all zeroes find the closest one
 while(!cZeroes.empty()) {
 nextPair = cZeroes.back();
 i = nextPair.first;
 j = nextPair.second;
 cZeroes.pop_back();
 std::vector< pair<T,T> >::iterator it = cOnes.begin();
 min = abs(it->first - i) + abs(it->second - j);
 while(it != cOnes.end()) {
 curDist = abs(it->first - i) + abs(it->second - j);
 if(curDist < min) min = curDist;
 it++;
 }
 A[i][j] = min;
 }
 //Print the result
 for(i = 1; i <= n; i++) {
 for(j = 1; j <= m; j++) {
 printf("%hu ", A[i][j]);
 A[i][j] = 0;
 }
 printf("\n");
 }
 }
 return 0;
}

Answer 1

I'd start by converting all the 1's in the input to some value that can't appear in the output (e.g., -1) and saving each of those locations.

Then I'd basically do a modified flood-fill, starting from each -1. Look at each of its neighbors, and any there are currently 0, set to 1 and save that location. Repeat for every other -1 in the input.

Then walk through all the saved locations. Each neighbor of those that's a zero, set to 2 (and, again, save those locations).

Repeat until you reach an iteration that doesn't find any more 0s in the input (and obviously, incrementing the distance number for each of these outer iterations).

Finally, change all the -1s back to 0s.

As far as your code itself goes, it's tagged C++, but a great deal of it is very C-like. You have a couple of vectors, but quite a few C-things that most C++ programmers would rather avoid (e.g., printf, scanf and built-in arrays). I'm also less than excited about some of the names you've used (e.g., cZeroes and currDist). I'd rather see the names spelled out more completely (e.g., current_distance or, if you insist on camelCase, currentDistance).

• mirgee: This is a nice simple little algorithm, but is it efficient? Also, I decided to use 'printf' and 'scanf' for speed. They are faster than 'cin' and 'cout', are they not?
• mirgee: I tried to implement your solution but it doesn't work very well. Could you please take a look at it? tny.cz/01cf7560
• ratchet freak: if it gives the correct output then ask a new question here; if it doesn't then try on SO, but you shouldn't do that for when A[i][j] is already !=0
• Jerry Coffin: @mirgee: printf/scanf can be faster, but if you're dealing with a 200x200 bitmap, you're only reading/writing something on the order of a kilobyte. Almost regardless of what you use, reading and writing a kilobyte (or so) shouldn't take up more than a few milliseconds of your 4 second allotment. I'd consider them if (and almost only if) I was at something like 4.002 seconds and 4 seconds was a hard limit, so I absolutely needed a minuscule improvement, regardless of the cost, and I saw no other easy optimizations.
• Jerry Coffin: @mirgee: As far as your implementation goes: when you say it doesn't work well, do you mean it's producing incorrect results, or it's producing correct results too slowly?