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.
C++ 