Szachowa gorączka

Pionek

Jeżeli $c_1=c_R$, to pionek może dostać się na żądane pole na dokładnie jeden sposób w $R-1$ ruchach. W przeciwnym przypadku, pionek nie może się dostać na żądane pole.

Wieża

Jeżeli $c_1=c_R$, to wieża może dostać się na żądane pole w jednym ruchu na dokładnie jeden sposób. W przeciwnym przypadku, może dostać się w dwóch ruchach na dwa sposoby.

Hetman

Hetman potrafi się dostać w takiej samej liczbie ruchów, co wieża, ale gdy wymaga dwóch ruchów, to czasem liczba sposobów jest większa, niż u wieży. Dla każdej kombinacji par ruchów (do góry, w lewo, w prawo, po przekątnej w lewo do góry, w prawo do góry) należy sprawdzić, czy hetman może się dostać na żądane pole korzystając z takich ruchów w takiej kolejności nie wychodząc poza planszę (przy czym jeżeli korzysta z dwóch ruchów po przekątnej, to trzeba jeszcze porównać parzystość liczb $1+c_1$ oraz $R+c_R$).

Goniec

Goniec może się dostać na żądane pole wtedy i tylko wtedy, gdy liczby $1+c_1$ oraz $R+c_R$ mają taką samą parzystość.

Bez straty ogólności załóżmy jaki jest pierwszy ruch gońca (po przekątnej w lewo, czy w prawo).

Żeby obliczyć minimalną liczbę ruchów, można rozważyć zachłanne zmienianie kierunku ruchu dopiero wtedy, gdy goniec uderzy w brzeg planszy. Niech $c_I$ będzie polem w wierszu $R$, w którym goniec skończy taki proces. Jeżeli $c_I=c_R$, to jest to najkrótsza i jedyna taka ścieżka. W przeciwnym przypadku, trzeba rozważyć dwa przypadki, zależnie od sposobu dotarcia do ostatniego wiersza. Jeżeli na przykład goniec dotarł do ostatniego wiersza poruszając się w prawo oraz żądane pole jest na prawo od ostatniej pozycji gońca (czyli $c_I<c_R$), to okazuje się, że goniec mógł dotrzeć do $c_R$ w takiej samej liczbie ruchów zmieniając czasem kierunek ruchu wcześniej, niż uderzając o brzeg ściany. Ale jeżeli goniec dotarł poruszając się w prawo oraz $c_I>c_R$, to trzeba wykonać jeden dodatkowy ruch, aby osiągnąć $c_I=c_R$.

Można w taki sposób wyliczyć minimalną liczbę ruchów $n$, jakie goniec musi wykonać, oraz dokładną liczbę pojedyńczych ruchów $f$, jakie goniec może pominąć przed uderzeniem w brzeg planszy. Takie pojedyńcze ruchy można pomijać wśród pierwszych $n-1$ ruchów (nie można się zatrzymywać przy ruchu, w którym goniec trafia do ostatniego wiersza), więc liczba ścieżek wynosi tyle, co liczba sposobów pominięcia $f$ pojedyńczych ruchów wśród pierwszych $n-1$ ruchów, co jest równoważne rozłożenia $f$ piłek do $n-1$ pojemników, czyli $(\genfrac{}{}{0ex}{}{f+n-2}{f})$.

Należy być ostrożnym przy przypadkach brzegowych takich jak zaczęcie lub skończenie przy brzegu planszy i kierunku dotarcia na żądane pole. Trzeba też mieć na uwadzę to, że w podanym wzorze liczba $n-2$ jest rzędu $O(\frac{R}{C})$, co jest duże, gdy $C$ jest małe. Żeby poradzić sobie z tym problemem, wystarczy rozłożyć $(\genfrac{}{}{0ex}{}{f+n-2}{f})$ na wyrażenie $\frac{(f+n-2)(f+n-3)\dots (n-1)}{f!}$, co ma tylko $O(C)$ czynników. Daje to rozwiązanie w złożoności $O(QC)$.

Król

Jeżeli $|c_R-c_1|\le R-1$, to aby wykonać jak najmniej ruchów, w każdym ruchu król musi wskoczyć do wyższego rzędu. Jeżeli $|c_R-c_1|>R-1$, to jest analogicznie, ale król za każdym razem musi przejść do kolejnej kolumny. Bez straty ogólności załóżmy, że $|c_R-c_1|\le R-1$ -- drugi przypadek można rozwiązać analogicznie.

W takim razie król wykonuje $R-1$ ruchów i jest pewna dowolność w poruszaniu się w lewo i prawo (jedyny warunek jest taki, że król ma trafić na pole $(c_R,R)$) i przy każdym ruchu porusza się w górę.

Można skorzystać z podejścia programowania dynamicznego. Niech $ways[i]$ wynosi liczbę sposobów dotarcia z pola początkowego na pole w $i$-tej kolumnie w aktualnym wierszu. Dla pierwszego wiersza zachodzi $ways[c_1]=1$ oraz $ways[i]=0$ dla $i\ne c_1$. Dla kolejnych zachodzi $nextways[i]=ways[i-1]+ways[i]+ways[i+1]$ zakładając, że $ways$ przyjmuje wartości $0$ dla indeksów spoza przedziału $[1,C]$. Wynikiem jest $ways[c_R]$ dla ostatniego wiersza. Daje to rozwiązanie w złożoności $O(RC)$ dla zapytania.

Rozszerzmy tablicę $ways[i]$ do tablicy $dp[start][i]$, która dla danego wiersza oblicza liczbę sposobów dotarcia na pole w kolumnie $i$ przy założeniu, że $c_1=start$. Pozwoli to spreprocessować odpowiedź dla wszystkich zapytań, ale też umożliwi to zastosowanie pewnej techniki.

Analogicznie zachodzi $nextdp[start][i]=dp[start][i-1]+dp[start][i]+dp[start][i+1]$. Daje to rozwiązanie w złożoności $O(R{C}^2+Q)$.

Zauważmy, że mając tablicę $dp$ obliczającą liczbę ścieżek od pierwszego wiersza do $r$-tego, można policzyć tablicę $doubledp$ od pierwszego wiersza do $2r-1$-tego. Można to wykonać iterując się po pozycji, w której pionek będzie się znajdywał w środkowym wierszu wśród tych $2r-1$ wierszy, a następnie przemnożyć ze sobą odpowiednie wartości tablicy $dp$, które tak naprawdę utrzymują liczbę sposobów, aby poruszyć się o $r-1$ wierszy do przodu. Daje to wzór $doubledp[start][i]=\sum _{mid=1}^{C}dp[start][mid]\cdot dp[mid][i]$.

Dzięki sposobowi podobnego do szybkiego potęgowania, można spreprocessować wyniki dla wszystkich zapytań w złożoności $O(C^3\log (R))$.

Aby przyśpieszyć rozwiązanie do $O(C^2\log (R))$, należy wykonać jeszcze kilka obserwacji dotyczących wyliczania tablicy $doubledp$. Można zacząć od wyliczenia wartości $doubledp[start][1]$ w czasie $O(C^2)$, co też od razu da wartości $doubledp[1][start]$, ponieważ ${\mathrm{\forall }}_{i,j}doubledp[i][j]=doubledp[j][i]$.

Dla $1<i<j<\frac{C}{2}$ zachodzi zależność $doubledp[start][j]=doubledp[start-1][j-1]+doubledp[1][1+i+j]$.

Analogicznie można wykazać, że dla $1<j<\frac{C}{2}$ oraz $j\le i\le C$ zachodzi $doubledp[start][j]=doubledp[start+1][j-1]+doubledp[1][1+start-j]$.

Wartości dla pozostałych par $(i,j)$ można już wtedy wyliczyć z symetryczności tablicy $doubledp$. Wyliczając wtedy $doubledp$ według konkretnej kolejności $i,j$ oraz korzystając z odpowiednich wzorków, można wyliczyć całe $doubledp$ w złożoności $O(C^2)$, co daje algorytm w złożoności $O(C^2\log (R)+Q)$.