Wyszukiwanie połączeń w tablicy dwuwymiarowej
Ostatnio zmodyfikowano 2015-12-02 11:16
Orzhov Temat założony przez niniejszego użytkownika |
Wyszukiwanie połączeń w tablicy dwuwymiarowej » 2015-11-30 20:12:45 Witam serdecznie, Pracuję nad programem, którego zadaniem jest zliczenie połączeń w tablicy dwuwymiarowej (takich samych znaków, w liniach prostych) Dla przykładu chcąc policzyć Y w takiej tablicy: X Y Y Y X Y X Y X X Y X X X X X X X Y Y X X X Y X Mamy 3 połączone grupy Y, 4 elementową, 3 elementową i 2 elementową A dla takiej X X Y Y X X X Y X Jedynie 3 grupy po 1 element. Tablica jest wypełniona jedynie 2 rodzajami znaków (puste / pełne). Utknąłem niestety odrobinę w martwym punkcie, stąd temat na forum z nadzieją że ktoś mnie naprowadzi na rozwiązanie. Chwilowo mam wprowadzenie danych do tablicy wielowymiarowej i algorytm ( nie napisany przeze mnie, gotowy) wyszukiwania Weighted Quick-Union with Path Compression. Całość kodu wygląda tak: #include <iostream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;
int x, y;
int rozmiar;
int cc;
int N;
vector < int > id;
vector < int > rk;
void init( int size )
{
cc = size;
N = size;
id.resize( size );
rk.resize( size );
for( int i = 0; i < N; i++ )
{
id[ i ] = i;
rk[ i ] = 0;
}
}
int find( int p )
{
while( p != id[ p ] )
{
id[ p ] = id[ id[ p ] ];
p = id[ p ];
}
return p;
}
bool connected( int p, int q )
{
return find( p ) == find( q );
}
void make_union( int p, int q )
{
int rootp = find( p );
int rootq = find( q );
if( rootp == rootq ) return;
if( rk[ rootp ] < rk[ rootq ] )
{
id[ rootp ] = rootq;
}
else if( rk[ rootp ] > rk[ rootq ] )
{
id[ rootq ] = rootp;
}
else
{
id[ rootq ] = rootp;
rk[ rootp ] ++;
}
cc--;
}
int main( int argc, char * argv[] )
{
int mapanieba[ rozmiar ][ rozmiar ];
cout << "Rozmiar";
cin >> rozmiar;
for( x = 0; x < rozmiar; x++ )
{
for( y = 0; y < rozmiar; y++ )
{
cin >> mapanieba[ x ][ y ];
}
}
int N = rozmiar * rozmiar;
init( N );
Oczywiście jest niedokończony, a ja nie umiem wpaść na to, co należy zrobić dalej, żeby móc "przepuścić" elementy tablicy przez algorytm i uzyskać liczbę połączeń. Znajdzie się ktoś kto poda pomocną dłoń i naprowadzi? |
|
darko202 |
» 2015-12-01 08:01:30 1.
za bardzo kombinujesz,
sam algorytm nie jest przecież strasznie trudny
idziesz po tablicy i sprawdzasz czy następna komórka ((według przyjętego kryterium - linia prosta) ma tą samą wartość np.
tab[i,j] == tab [i+1,j]
2.
nie wiem jaki algorytm wykorzystałeś, ale to co zaprezentowałeś to działanie po jednym wymiarze i nie za bardzo widzę związek z Twoim zadaniem.
zapomnij o nim i zacznij od nowa
a. tworzysz tablicę
b. wypełniasz ją
c. sprawdzenie
tab[i,j] == tab [i+1,j]
d. może też sprawdzenie
tab[i,j] == tab [i,j+1]
Powodzenia :)
|
|
Szadziu |
» 2015-12-01 13:35:28 Leć po kolei po każdym elemencie tablicy. Jeśli znajdziesz Y to dodaj stwórz jakiś element mówiący ci o połączeniu, ustaw mu wartość na 1. Zamień ten elemeny na jakiś inny np. Z. Następnie sprawdź jego otoczenie ( 8 elementów ) czy któryś jest Y. Jeśli tak zrób to samo co dla tego elementu. Powtarzaj aż ilość będzie 0. Następnie sprawdzaj kolejne elementy tablicy. |
|
ArgonZapan |
» 2015-12-01 20:11:02 @darko202 - twój algorytm wykaże 5 połączeń dla 1 przykładu
@Szadziu - Tu się zgodzę, tylko że otoczenie dla 4 elementów |
|
1aam2am1 |
» 2015-12-01 20:28:22 Prosty algorytm rekursywny
1. Początek.
2. Aktualna pozycja usuń znak.
3. Jeżeli lewo jest znakiem szukanym -> algorytm();
4. Jeżeli prawo jest znakiem szukanym -> algorytm();
5. Jeżeli góra jest znakiem szukanym -> algorytm();
6. Jeżeli dół znakiem szukanym -> algorytm();
7. Zmienna++;
8. Koniec. |
|
Szadziu |
» 2015-12-02 11:16:34 Zależy czy chcesz ukośne też znajdować |
|
| « 1 » |