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).