Fox Ciel is sailing in the Donut sea. The Donut sea is a torus. For navigation, the torus is divided into N times M cells, as shown in the figure below.
(Image by YassineMrabet from Wikimedia Commons, licensed under CC BY-SA 3.0.)
Each of the cells has two integer coordinates (n, m), where 0 <= n < N and 0 <= m < M. Note that the coordinates wrap around modulo N and M. For example, if you are in the cell (N-1, M-1) and you cross over one of its sides, you will reach one of the cells (N-2, M-1), (0, M-1), (N-1, M-2), and (N-1, 0).
Ciel starts in the cell (0, 0) and wants to reach the goal cell (goalX, goalY).
Unfortunately, Ciel's navigation is very poor. Whenever she moves to a new cell, there are two equally probable outcomes: either her first or her second coordinate increases by one (wrapping around if necessary). Formally, if Ciel's current coordinates are (n, m), her new coordinates will be either ((n+1) modulo N, m), or (n, (m+1) modulo M), with equal probability. Each such move takes one day.
Return the expected number of days Ciel will need to reach her goal.
|