W dniu sobota, 11 maja 2013 18:12:55 UTC+2 użytkownik Vax napisał:
> Haczyk polega na tym, że już wstępnie maksymalna liczbę iteracji możemy
> ograniczyć do 2^(min(M,N)) gdzie min() zwraca mniejszy z argumentów.
> Dlaczego? Ano dlatego, że aby zadanie w ogóle zostało spełnione to obraz
> zapalonych/zgaszonych komórek po wykonaniu "klików" na pierwszym rzędzie
> determinuje wymagane "kliki" rzędu 2, ten zaś narzuca kolejny
Dobre spostrzezenie.

Ciekawe jak to mozna wykorzystac do zwyklego algorytmu ze spamietywaniem,
a moze nawet bez spamietywania.

Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
breanch-faktor.

Pozostaje kwestia czy mozna jakos uniknac spamietywania?

Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
wymagaloby sporo pamieci.

Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.

Pozdrawiam