losowanie tablicy

Odpowiedz Nowy wątek
2007-01-07 16:31
0

Mam problem do rozwiązania:

potrzebuję funkcji która wygeneruje mi 2 wymiarową tablicę n * m gdzie:
1) każda komórka tablicy może posiadac dwa stany: 1 - jest klocek, 2 - nie ma klocka
2) ilość klocków w całej tablicy powinna być dokladnie ustalona
3) ilość kolocków w każdej kolumnie powinna być dobierana losowo z zakresu 0 - n uwzględniając warunek drugi
4) ilość kolocków w każdym wierszu powinna być dobierana losowo z zakresu 0 - m uwzględniając warunek drugi
5) klocki w poszczególnych wierszach i kolumnach powinny bezpośrednio ze sobą sąsiadować tworząc w ten sposób jedną albo dwie (oddzielone od siebie dowolną ilością zer) grupy klocków

W takich przypadkach zawsze można zrobić to algorytmem brute force, ale niestety i tutaj jest on do tego zbyt wolny. Ma ktoś jakis pomysł?

Pozostało 580 znaków

2007-01-07 23:37
berbelek
0

Na początek zakładamy, że każde pole jest puste.

  1. Losujemy dowolne pole i zapełniamy je.
  2. Tworzymy listę składającą się z pól otaczających wylosowane przed chwilą pole (z polami sąsiadującymi po skosie lub bez, wedle potrzeb)
  3. Kolejne pole do zapełnienia losujemy tylko z listy utworzonej w poprzednim punkcie (dzięki temu spełniony będzie warunek 5)
  4. Modyfikujemy listę
    • usuwamy z niej pole zapełnione w punkcie 3
    • dodajemy pola otaczające przed chwilą zapełnione pole (pod warunkiem, że nie są już zapełnione)
  5. Powtarzamy kroki 3 - 4 do momentu zapełnienia wymaganej warunkiem 2 liczby pól

Oczywiście trzeba też pamiętać, o usuwaniu z listy pól spoza krawędzi tablicy.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0