位图问题性能提升

Question

问题陈述输入是一个矩形位图，如: 0001 0011 0110，任务是为每个黑色(0)“像素”找到距离最近的白色(1)“像素”。因此，上面的输出应该是:3 2 1 0 2 1 0 0 1 0 0 0 1

下面是一个工作的，评论很多的78行解决方案.不过，这太天真了。我怎样才能让它更快？我知道我可以在以给定的零为中心的矩形中搜索，但我不确定我是否需要它那么复杂。我只想在4s下运行它，在奔腾III上输入200*200。

#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

首先，将输入中的所有1's转换为输出中不能显示的值(例如-1)，并保存每个位置。

然后，从每个-1开始，我基本上会做一个修改过的洪水填充。查看它的每个邻居，其中任何一个当前为0，设置为1并保存该位置。对输入中的每个其他-1重复。

然后遍历所有保存的地点。这些值为零的每个邻居，设置为2(并且，再次保存这些位置)。

重复，直到到达一个没有在输入中找到任何0s的迭代(显然，增加这些外部迭代的距离数)。

最后，把所有的-1s都换成了0s。

就您的代码本身而言，它被标记为C++，但是很多代码都非常类似于C。您有几个vectors，但是大多数C++程序员宁愿避免的一些C-东西(例如，printf、scanf和内置数组)。对于您使用过的一些名称(例如，cZeroes和currDist)，我也不太兴奋。我更希望看到更完整的名字(例如，current_distance，或者，如果您坚持camelCase，currentDistance)。