Se cunoaşte că regele se poate mişca pe tabla de şah doar în câmpurile învecinate pe toate cele $8$ direcţii. În figura de mai jos putem vedea deplasările posibile ale regelui la o mutare. Numim drum o succesiune de una sau mai multe astfel de mutări.

p=. !problema/rege?rege.png 40%!
 

h2. Cerinţă
Cunoscând dimensiunea $M$ x $N$ a tablei de şah, respectiv poziţia iniţială (l{~1~}, c{~1~}) şi poziţia finală (l{~2~}, c{~2~}) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.

h3. Explicaţie

1. (3, 3) - (3, 4) - (2, 5)
2. (3, 3) - (2, 4) - (2, 5)

...

== include(page="template/taskfooter" task_id="rege") ==

4876