losowanie tablicy

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ł?

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.

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