Matematyka.pl

Na szachownicy o wymiarach 201 wierszy i 201 kolumn umieszczono pewną liczbę wież
szachowych tak, że każde z pól jest szachowane. Przyszedł zły człowiek i zmienił położenie jednej z
wież na szachownicy, tak że nie wszystkie pola są szachowane. Proszę zaproponować funkcję, która
znajdzie przeniesienie jednej wieży tak aby ponownie wszystkie pola były szachowane. Do funkcji
przekazujemy tablicę bool t[201][201] z układem wież po zmianie, funkcja powinna wyznaczyć i
zwrócić dwa pola (wiersz, kolumna) – skąd , dokąd należy przenieść wieżę.

Byłbym bardzo wdzięczny chociaż za jakiś pomysł.

Po przesunięciu będzie istnieć kolumna, w której są co najmniej dwie wieże, wiersz, w którym są co najmniej dwie wieże i wieża na przecięciu tej kolumny z tym wierszem. To jest nasza ruszona figura.
Teraz patrzysz, które pola nie są szachowane — będą wszystkie w jednym wierszu i w jednej kolumnie. To stamtąd została ruszona nasza bierka.

Zauważ, że w zadaniu nie ma mowy o tym, że ustawienie wież było optymalne, tzn. nie jest pewne, czy nie ma nadmiarowych wież, więc kolumn i wierszy ze zdublowanymi figurami może być więcej niż jedna.