Manhattan Distance

Witam, próbuję rozwiązać problem BITMAPA z platformy spoj.com http://pl.spoj.com/problems/BITMAP/
Napisałem program w DevC++, który niestety nie działa, szukałem już wszędzie jakiegoś błędu, ale nic nie mogłem znaleźć. Jak mam daną tablicę i deklaruję statyczne tablice, zamiast dynamicznych (z **)- wszystko jakby było ok.Zadanie próbowałem rozwiązać w ten sposób, że znajduje każdy manhattan-distance dla każdego punktu- zapisuje je do tablicy 1- wymiarowej, a następnie zwraca jej minimalną wartość. (Wiem, że mój algorytm ma dość dużą złożoność obliczeniową, ale nie mam na razie pomysłu na nic lepszego). Mój problem polega na tym, że po wprowadzeniu danych program przestaje działać (wyświetla się komunikat "Program .... przestał działać. Trwa wyszukiwanie rozwiązania...."). Ale niestety nic nie znajduję. Byłbym wdzięczny, gdyby ktoś zechciał udzielić mi jakiejś wskazówki.
Zamieszczam kod źródłowy ze statycznymi i danymi tablicami:

 #include <iostream>
#include <cstdlib>
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int the_least_value(int*t, int n)
{
    
    int min=0;
    for(int i=0;i<n;i++)
    {
        
            if(t[i]<t[min])
            
                min=i;
            
        }
    
    return t[min];
}
int mandis(int **t, int n, int i, int j)
{
    int k,l, pom=0;
    int wyniki[8*n];
for(k=0;k<n;k++)
{
    for(l=0;l<n;l++)
    {
if(t[k][l]==1)
{
    wyniki[pom]=abs(i-k)+abs(j-l);
    pom++;
}
}
}
return the_least_value(wyniki,pom+1);


}


int main(int argc, char** argv) {
    int **t=new int *[6];
    for(int i=0;i<3;i++)
    t[i] = new int [6];
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            t[i][j]=0;
            
    t[1][1]=1;
    t[3][4]=1;
    t[4][4]=1;
    t[2][5]=1;
    t[4][3]=1;
    t[5][5]=1;
    
    
        
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
            {cout<<"   "<<t[i][j];
            }cout<<endl;
    }
    cout<<"\n\n\n\n\n";
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
            {cout<<"   "<<mandis(t,6,i,j);
            }cout<<endl;
    }
    
    return 0;
}

oraz kod źródłowy z dynamicznymi tablicami i możliwością wprowadzania danych:

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int least_value(int *t, int n)
{
    int min=0;
    for(int i=1;i<n;i++)
    if(t[i]<t[min])
    min=i;
    return t[min];
}
int dis(int **t, int n, int m, int i, int j)
{
    int k,l,pom=0;
    int *wyniki=new int[6];
    for(k=0;k<n;k++)
    {
        for(l=0;l<m;l++)
        {
            if(t[k][l]==1)
            {
                wyniki[pom]=abs(i-k)+abs(j-l);
                pom++;
            }
        }
    }
    return least_value(wyniki,pom);
}


int main()
{
    int number_of_tests, rows, columns;
    int **t=new int*[3];
    
    string a;
    int *temp=new int[3];
    
    cin>>number_of_tests;
    
    for(int q=0;q<number_of_tests;q++)        //repeat whole test
    {

    cin>>rows>>columns;
        for(int e=0;e<rows;e++)
        {
        cin>>a;
        
            for(int o=0;o<columns;o++)
            {
                t[e][o]=a[o];
            }
        }
    
    
    
    
    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<columns;j++)
        {
            cout<<dis(t,rows, columns, i, j);
        }cout<<endl;
    }
    }
    delete *t;
    delete t;
    return 0;
} 

Z góry dziękuję i pozdrawiam.

Liczysz to tak:

• dla każdego białego bitu ustawiasz odległość od najbliższego białego piksela równą 0
• dla wszystkich sąsiadów, którzy nie są biali ustawiasz odległość równą 1
• dla wszystkich sąsiadów ww punktu dla wszystkich sąsiadów:
  • jeśli mają ustawioną wartość to ustawiasz wartość na mniejszą z 2: tą, która jest przypisana lub sąsiada + 1
  • jeśli jest bez wartości to sąsiad + 1

Złożoność .

Dzięki za odpowiedź- spróbuję wykombinować jakoś implementacje tego algorytmu. Ten Twój pomysł wymaga implementacji kolejki? A jeszcze takie drobne pytanko, mógłbyś mi doradzić jak wczytywać wpisywane wartości po jednym znaku? Bo dla każdego wiersza zera i jedynki są wprowadzane jednym ciągiem, jak to zamienić, że pierwszy znak jest do 1. kolumny, 2. do drugiej itd.? Chciałem to zrobić poprzez konwersje stringu na int, ale coś mi nie wychodziło. Przypuszczam, że jest jakieś proste rozwiązanie tego problemu, ale nie zdołałem go znaleźć.
Pozdrawiam

A i mógłbyś mi powiedzieć, czy zauważasz jakieś błędy w implementacji, którą zamieściłem?

Jeśli chodzi o konwersję to:

• string w C++ można utożsamić z tablicą znaków
• '0' - '0' = 0 i '1' - '0' = 1

Niestety słabo mogę pomóc bo ten kod jest paskudnie sformatowany i nie da się go czytać. Popraw go samemu, bo ja na to nie mam czasu.

Poza tym kolejkę masz wbudowaną w STLa więc nic pisać nie trzeba.

Poporiawiałem błędy w kodzie i jak sprawdzam wszystko działa, ale jak wrzucam na spoja wyświetla się komunikat SIGABART, co może być tego powodem?
Wrzucam poprawiony kod:

#include <cstdlib>
#include <iostream>
using namespace std;

int least_value(int *t, int n)
{
    int min=0;
    for(int i=1;i<n;i++)
    if(t[i]<t[min])
    min=i;
    return t[min];
}
int dis(int **t, int n, int m, int i, int j)
{
    int k,l,pom=0;
    int *wyniki=new int[182];
    for(k=0;k<n;k++)
    {
        for(l=0;l<m;l++)
        {
            if(t[k][l]==1)
            {
                wyniki[pom]=abs(i-k)+abs(j-l);
                pom++;
            }
        }
    }
    return least_value(wyniki,pom);
    delete wyniki;
}


int main()
{
    int number_of_tests, rows, columns;
    
    int **t;
    t=new int*[182];
    for(int it=0;it<182;it++)
    t[it]=new int[182];
    
    char *a=new char[3];
    
    for(int i=0;i<rows;i++)
    for(int j=0;j<columns;j++)
    t[i][j]=0;
    
    cin>>number_of_tests;
    
    for(int q=0;q<number_of_tests;q++)        //repeat whole test
    {

    cin>>rows>>columns;
        for(int e=0;e<rows;e++)
        {
        cin>>a;
        
            for(int o=0;o<columns;o++)
            {
                t[e][o]=a[o]-48;
            }
        }
    
    cout<<endl;

    
    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<columns;j++)
        {
            cout<<dis(t,rows, columns, i, j);
        }cout<<endl;
    } 
    }
    for(int it=0;it<182;it++)
    delete [] t[it];
    delete [] t;
//    system("pause");
    return 0;
}