Problem description

Back
Show PDF
Mało ryb
(B)
Limit pamięci: 256 MB
Limit czasu: 2.50 s

Jednym z podstawowych elementów przetrwania w grze Minecraft jest unikanie głodu. Alex odczuwa głód, dlatego postanowiła złowić ryby w pobliskim jeziorze. W rejonie jeziora, w którym się znajduje, ryb jest jednak niewiele, dlatego postanowiła przepłynąć na jego przeciwległy róg i spróbować łowić tam.

Jezioro ma kształt prostokąta o wymiarach N × M bloków. Początkowo łódka Alex znajduje się w bloku położonym w rogu jeziora o współrzędnych (1,1), a celem jest dopłynięcie do przeciwległego rogu jeziora, czyli bloku o współrzędnych (N,M). Alex może poruszać się wyłącznie w górę, w dół oraz na boki i nie może opuszczać łódki. Jezioro znajduje się w biomie tajgi, w związku z czym część jego bloków stanowią bloki lodu, przez które łódka nie może przepłynąć, a pozostałe bloki są blokami wody.

Alex ma zużyty kilof, za pomocą którego może niszczyć bloki lodu, torując sobie drogę. Kilof jest niemal całkowicie wyczerpany, dlatego Alex może zniszczyć jedynie 2 bloki lodu. Ponadto, z powodu ograniczonego miejsca w ekwipunku, postanowiła zniszczyć dokładnie 2 bloki lodu, żeby w pełni zużyć kilof.

Alex zastanawia się, na ile różnych sposobów może to osiągnąć. Pomóż jej i wyznacz liczbę par bloków lodu, znajdujących się w dowolnym miejscu w obszarze jeziora, po których zniszczeniu Alex będzie mogła przepłynąć przez jezioro.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oznaczające wymiary jeziora.

Następne N wierszy opisuje jezioro, każdy wiersz zawiera M znaków . lub X, j-ty znak w i-tym wierszu (Bi, j) określa, czy blok o współrzędnych (i,j) jest blokiem wody (Bi, j= .) czy blokiem lodu (Bi, j= X).

Jest gwarantowane, że B1, 1 = BN, M= .

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się pojedyncza liczba całkowita oznaczająca liczbę różnych par bloków lodu, po których zniszczeniu Alex może przepłynąć z (1,1) do (N,M).

Ograniczenia

1 ≤ N ⋅ M ≤ 250 000, 1 ≤ N, M

Podzadania

Podzadanie Warunki Punkty
1 Po zniszczeniu dowolnego bloku lodu można dopłynąć z (1,1) do (N,M) 5
2 N ≤ 2 16
3 N ⋅ M ≤ 10 000 29
4 Brak dodatkowych ograniczeń 50

Przykłady

Wejście Wyjście Wyjaśnienie 
3 5
..X..
.XX..
..XX.


7

Jedyne pary bloków lodu po zniszczeniu których można przepłynąć z (1,1) do (3,5) to: (1,3) i (2,2), (1,3) i (2,3), (1,3) i (3,3), (1,3) i (3,4), (2,2) i (2,3), (2,3) i (3,3) oraz (3,3) i (3,4).
Wejście Wyjście Wyjaśnienie 
3 2
..
X.
..

0

Nie da się zniszczyć dokładnie dwóch bloków lodu, ponieważ jest tylko jeden blok lodu.
Wejście Wyjście Wyjaśnienie 
5 7
.....X.
.XX.XX.
X..X.X.
.XX.XX.
.....X.

17

Żeby można było przepłynąć z (1,1) do (5,7), trzeba zniszczyć przynajmniej jeden blok lodu z kolumny j = 6. Jeśli zniszczony zostanie blok (1,6), to drugi blok w parze może być dowolny (12 kombinacji). Jeśli nie zostanie zniszczony blok (1,6), ale zostanie zniszczony blok:

  • (2,6), to musi zostać zniszczony blok (2,5) (1 opcja)
  • (3,6), to musi zostać zniszczony blok (3,4) albo (2,5) (2 opcje)
  • (4,6), to nie można zniszczyć jeszcze jednego bloku, by dało się przepłynąć z (1,1) do (5,7) (0 opcji)
  • (5,6), to musi zostać zniszczony blok (3,1) albo (3,4) (2 opcje).

12 + 1 + 2 + 0 + 2 = 17