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.
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 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 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 ${f+n-2 \choose 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ć ${f+n-2 \choose 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)$.
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\neq 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(RC^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ż $\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)$.