program zliczający jedynki sąsiadujące ze sobą

czesc, mam za zadanie napisac program w c++.
wyjasnie od poczatku o co w nim chodzi:

• na konsoli wprowadza sie dowolna liczbe calkowita dodatnia, np. 5
  oraz kwadrat utworzony z jedynek i zer oddzielonych spacjami np.
  0 1 0 1 1
  0 0 0 1 1
  1 0 1 0 1
  0 1 1 1 0
  0 0 0 1 0
  gdzie dlugosc boku okreslona jest przez wczesniej podana liczbe.
• program powinien policzyc ilosc grup jedynek (jedynki sa w jednej grupie gdy sasiaduja ze soba w pionie lub poziomie) jak rowniez podac ilosc jedynek w najwiekszej grupie. Czyli dla podanego wczesniej przykladu program powinien wypisac: 4 5
  dzieki z gory za wszelkie wskazowki :)

Napisz kod ktury już masz bo wygląda to na chęć otrzymania gotowca

1. Wczytujesz liczbę n z konsoli.
2. Wczytujesz n linii z konsoli.
3. Parsujesz te linie, to znaczy - wpisujesz do macierzy zerojedynkowej, gdzie jaka jedynka siedzi (w zależności od pozycji jedynki w każdej linii i od numeru linii).
4. Sprawdzasz jakimś algorytmem *, jakie są grupy jedynek, i wypisujesz je w tablicy - każda pozycja to liczba jedynek w danej grupie oraz wektor ich współrzędnych. Wypisujesz liczbę grup - po prostu długość tablicy - i wypisujesz największą.

• jakimś algorytmem - na tym forum był kilkanaście dni temu temat z podobnym algorytmem, niestety nie pamiętam, jakim, ale może sam coś wymyślę w najbliższym czasie, jak nie znajdę.

EDIT:

Mój algorytm wygląda tak (nie wiem, czy zadziała):
4. Dla każdej linii sprawdzasz po kolei elementy. Jeśli trafi się jedynka, to:
4.1. Sprawdzasz, czy przedtem nie było w tej linii jedynki (innej grupy) w poprzednim elemencie. Jeśli była, to zwiększasz liczność tej poprzedniej grupy i dodajesz współrzędne jedynki.
4.2. Potem sprawdzasz, czy dla danej kolumny nie było jedynki (grupy) w poprzedniej linii. Jeśli była, to zwiększasz liczność tej grupy z poprzedniej linii i dodajesz współrzędne jedynki.
4.3. Jeśli żadne z powyższych, to tworzysz nową grupę o liczności 1 i dodajesz współrzędne jedynki.

Jest to napisane na szybko, proste, nieefektywne, ale mam nadzieję - zadziała. Pytaj, jak coś trzeba wyjaśnić.

Mały Lew napisał(a):

Napisz kod ktury już masz bo wygląda to na chęć otrzymania gotowca

Nie mam zadnego kodu, ale nie oczekuje tez gotowaca :) po prostu licze na wskazowki z jakich funkcji skorzystac itp. Bo nie wiem jak sie do tego zabrac :)

Michał Bodziony napisał(a):

1. Wczytujesz liczbę n z konsoli.
2. Wczytujesz n linii z konsoli.
3. Parsujesz te linie, to znaczy - wpisujesz do macierzy zerojedynkowej, gdzie jaka jedynka siedzi (w zależności od pozycji jedynki w każdej linii i od numeru linii).
4. Sprawdzasz jakimś algorytmem *, jakie są grupy jedynek, i wypisujesz je w tablicy - każda pozycja to liczba jedynek w danej grupie oraz wektor ich współrzędnych. Wypisujesz liczbę grup - po prostu długość tablicy - i wypisujesz największą.

• jakimś algorytmem - na tym forum był kilkanaście dni temu temat z podobnym algorytmem, niestety nie pamiętam, jakim, ale może sam coś wymyślę w najbliższym czasie, jak nie znajdę.

EDIT:

Mój algorytm wygląda tak (nie wiem, czy zadziała):
4. Dla każdej linii sprawdzasz po kolei elementy. Jeśli trafi się jedynka, to:
4.1. Sprawdzasz, czy przedtem nie było w tej linii jedynki (innej grupy) w poprzednim elemencie. Jeśli była, to zwiększasz liczność tej poprzedniej grupy i dodajesz współrzędne jedynki.
4.2. Potem sprawdzasz, czy dla danej kolumny nie było jedynki (grupy) w poprzedniej linii. Jeśli była, to zwiększasz liczność tej grupy z poprzedniej linii i dodajesz współrzędne jedynki.
4.3. Jeśli żadne z powyższych, to tworzysz nową grupę o liczności 1 i dodajesz współrzędne jedynki.

Jest to napisane na szybko, proste, nieefektywne, ale mam nadzieję - zadziała. Pytaj, jak coś trzeba wyjaśnić.

Dzieki wielkie, sprobuje w najblizszych dniach napisac ten program :) jak gdzies utkne to nie omieszkam poprosic jeszcze o pomoc :) pozderki :)

dostalem podpowiedz z czego powinienem korzystac, a wiec dane powinienem zapisac w tablicy jednowymiarowej i powininem skorzystac z weighted quick union with path compression. stworzylem poczatek mojego algorytmu, w ktorym dane wpisuje do tablicy jednowymiarowej, jak rowniez tworze komponenty jedynek w poziomie. niestety cos w nim jest nie tak :( ale nie wiem co

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

                int cc;			// number of components
                int N;			// number of elements
                int size;
                vector<int> id; // id[i] = parent of i
                vector<int> rk; // rk[i] = rank of subtree rooted at i

                // initializes data structures
                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;
                    }
                }

                // gets component's identifier of the element
                int find(int p)
                {
                    while (p != id[p])
                    {
                        id[p] = id[id[p]];    // path compression by halving
                        p = id[p];
                    }
                    return p;
                }

                // check if 2 elements belongs to the same component
                bool connected(int p, int q)
                {
                    return find(p) == find(q);
                }

                // connect components
                void make_union(int p, int q)
                {
                    int rootp = find(p);
                    int rootq = find(q);
                    if (rootp == rootq) return;

                    // make root of smaller rank point to root of larger rank
                    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 liczba;
    cin >> liczba;
    int size = liczba*liczba;
    void init(int size);
    void find();
    bool connected();
    int tablica [size];

    for (int i=0; i<size; i++)
    {
        int a;
        cin >> a;
        tablica[i] = a;
    }
    cout << tablica[0] << tablica[1] << tablica[2] << endl;

    for ( int i=0; i<(size-1); i++)
    {
        int i2 = i+1;
        if (tablica[i] == '1' && tablica[i2] == tablica[i] && tablica[i2]%liczba!=0)
        make_union(i, i2);

    }


    cout<<tablica[6]<<tablica[7]<<tablica[8]<<cc<<N<<endl;
    cout<<size<<endl;


    return cc;
}

Rozważ taki początek:

#include <map>
#include <set>
#include <iostream>
using namespace std;

typedef set<unsigned> neighborhood;
struct node
  {
   neighborhood neighbors;
   unsigned size;
   node(unsigned with,unsigned y,unsigned x):size(1)
     {
      neighbors.insert(id(with,y-1,x));
      neighbors.insert(id(with,y+1,x));
      neighbors.insert(id(with,y,x-1));
      neighbors.insert(id(with,y,x+1));
     }
   static unsigned id(unsigned with,unsigned y,unsigned x) { return y*with+x; }
  };
typedef pair<unsigned,node> item;
typedef map<unsigned,node> groups;

int main()
  {
   size_t size,with;
   cin>>size;
   with=size+2;
   groups grp;
   unsigned v;
   for(unsigned y=1;y<=size;++y)
     {
      for(unsigned x=1;x<=size;++x)
        {
         cin>>v;
         if(v) grp.insert(item(node::id(with,y,x),node(with,y,x)));
        }
     }
...