W dniu 2013-05-12 16:44, bartekltg pisze:

> Nie ja nie rozumiem, tylko Ty masz nieporządek.
> Deklarowałeś złożność 2^n. (n<=m) a to nie może być osiagniete,
> jeśli pamiętasz jedną linię. Wtedy masz m*2^n (m>=n)
> Tylko tyle;)

Właśnie gdy pamiętam jedną linię jest osiągnięte.
Cała "iteracja wewnętrzna" to nie szukanie rozwiązania, ale jego test.

W "klasycznej" metodzie, gdzie szukasz kombinacji kliknięć po całej
tablicy, musisz te kliknięcia tak czy siak "zrzutować" na tablicę
wejściową by sprawdzić, czy tablica ma wymagany stan (same jedynki, lub
same zera, jak tam założysz).
Zauważ, że iteracyjne przetworzenie rzędów jest odpowiednikiem
iteracyjnego sprawdzenia "sekwencji klików" (i dużo szybsze niż test
przeciętnej sekwencji N*M potencjalnych klików).

Jako, że czasochłonność testu jest zależna od rozmiaru danych (w jednym
wypadku od liczby bitów na każdy bok, w drugim od ich iloczynu) koszt
testu pominąłem, istotne, że ja mam do przetestowania np. 16 kombinacji
zamiast np. 65536 (i to zapewne przy większym koszcie testu w druim
przypadku).

> Zalapalem, ale pisać nie bronię:)

w sąsiedniej gałęzi wątku wyłuszczyłem, mam nadzieję, że wystarczająco?

> Twój alg jest prosty i rzeczywiśćei łątwo go się optymalizuje sprzętowo,
> ale pisałem to wszytko po to, byś zobaczył, gdzie bardziej
> zaawansowany algorytm zyskuje przewagę.

"Pominąłeś koszty operacji macierzowych" ;)

> Wyciąłeś to, więc zakładam, że załapałeś.

załapałem, wiem o czym piszesz, ale jestem zwolennikiem wstępnego
upraszczania problemów na drodze logicznej, a to był akurat dobry
przykład :)