Jak to zrobić na 10 punktów?

Ja miałem tylko pomysł na 5 punktów, żeby bezpośrednio zapamiętywać, z których obszarów da się dojść o obu osad--nazwijmy te obszary "dobrymi"--i dla każdej odległości od pierwszej osady, ile jest dobrych obszarów w tej odległości od niej. Wtedy niszczymy warownię wtedy i tylko wtedy, kiedy jest byłaby ona na jedynym dobrym obszarze o tej odległości od pierwszej osady.

Jeśli nie burzymy warowni, możemy aktualizować złe obszary DFS-em takim, że jeśli zaznaczamy jako zły obszar o pozycji (i, j), to jeśli obszar na prawo do góry, czyli (i - 1, j + 1) jest zły, to zaznaczamy jako złe obszary (i - 1, j) i (i, j + 1), jeśli jeszcze nie były zaznaczone jako złe oraz analogicznie jeśli obszar czyli (i + 1, j - 1) jest zły, to zaznaczamy jako złe obszary (i + 1, j) i (i, j - 1), jeśli jeszcze nie były zaznaczone jako złe.

Moje rozwiązanie: Utrzymujemy "najbardziej górną" i "najbardziej dolną" możliwą trasę między osadami. Nowa warownia będzie wyburzona wtw. gdy leży na obu z nich.

Dla ustalenia uwagi, skupmy się na "najbardziej górnej" trasie. Możemy ją trzymać na drzewie przedziałowym, dla każdej kolumny trzymając maksymalny wiersz przez który przebiega trasa w tej kolumnie. Trzymamy również wszystkie warownie, które leżą pod trasą, bo być może później będą musiały być ominięte.

Kiedy dochodzi nowa warownia (R,C) przecinająca trasę, jej aktualizacja wymaga obniżenia trasy do poziomu co najmniej (R+1) na odcinku [C-1,M]. Jeśli istniały jakieś warownie na odcinku (0,C-1) - (R+1,C-1) lub (R+1,C-1) - (R+1,M), które wcześniej były pod trasą, to je też musimy ominąć (i jednocześnie wyrzucić z listy warowni pod trasą, żeby rozpatrzeć je co najwyżej raz).

Można też mieć std::map z wierzchołkami trasy zamiast drzewa przedziałowego. Ale iterowanie po sąsiednich elementach mapy przy modyfikacjach bywa dość bugogenne ;)

Ja moge dodać jeszcze, że w tym zadaniu symetria jest wygodna w implementacji - jeśli mamy obsługę górnej trasy dla nowej wartowni (R, C) to obsługę dolnej/lewej trasy można zaimplementować jako obsłużenie punktu (C, R).

Ja trzymałem na secie par intów wszystkie punkty, w których ścieżka skręca. Kod wyszedł na tyle prosty, że mogłem bez większych problemów po prostu skopiować i przerobić dla dolnej ścieżki.

Nie trzeba wprost utrzymywać ścieżek. Wystarczy dla każdego wiersza/kolumny utrzymywać najbardziej wysuniętą warownie, będącą w obszarze ścieżki (tzn warownia należy do obszaru górnej ścieżki gdy na niej leży lub jest powyżej), a dla warowni czy należy do obszaru górnej lub dolnej ścieżki.
Aktualizować strukturę możemy dfs-em, który odwiedza warownie i sprawdza czy można coś zaktualizować. Aby znajdować "sąsiadów" wierzchołka w dfs-ie utrzymywałem dla każdego wiersza/kolumny set zawierający warownie w tym wierszu/kolumnie.