CF1245E.Hyakugoku and Ladders

Hyakugoku has just retired from being the resident deity of the South Black Snail Temple in order to pursue her dream of becoming a cartoonist. She spent six months in that temple just playing "Cat's Cradle" so now she wants to try a different game — "Snakes and Ladders". Unfortunately, she already killed all the snakes, so there are only ladders left now.

The game is played on a $10 \times 10$ board as follows:

• At the beginning of the game, the player is at the bottom left square.
• The objective of the game is for the player to reach the Goal (the top left square) by following the path and climbing vertical ladders. Once the player reaches the Goal, the game ends.
• The path is as follows: if a square is not the end of its row, it leads to the square next to it along the direction of its row; if a square is the end of its row, it leads to the square above it. The direction of a row is determined as follows: the direction of the bottom row is to the right; the direction of any other row is opposite the direction of the row below it. See Notes section for visualization of path.
• During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is $r$. If the Goal is less than $r$ squares away on the path, the player doesn't move (but the turn is performed). Otherwise, the player advances exactly $r$ squares along the path and then stops. If the player stops on a square with the bottom of a ladder, the player chooses whether or not to climb up that ladder. If she chooses not to climb, then she stays in that square for the beginning of the next turn.
• Some squares have a ladder in them. Ladders are only placed vertically — each one leads to the same square of some of the upper rows. In order for the player to climb up a ladder, after rolling the dice, she must stop at the square containing the bottom of the ladder. After using the ladder, the player will end up in the square containing the top of the ladder. She cannot leave the ladder in the middle of climbing. And if the square containing the top of the ladder also contains the bottom of another ladder, she is not allowed to use that second ladder.
• The numbers on the faces of the dice are 1, 2, 3, 4, 5, and 6, with each number having the same probability of being shown.

Please note that:

• it is possible for ladders to overlap, but the player cannot switch to the other ladder while in the middle of climbing the first one;
• it is possible for ladders to go straight to the top row, but not any higher;
• it is possible for two ladders to lead to the same tile;
• it is possible for a ladder to lead to a tile that also has a ladder, but the player will not be able to use that second ladder if she uses the first one;
• the player can only climb up ladders, not climb down.

Hyakugoku wants to finish the game as soon as possible. Thus, on each turn she chooses whether to climb the ladder or not optimally. Help her to determine the minimum expected number of turns the game will take.

百谷刚刚从南黑蜗牛寺的驻寺神明职位上退休，以追求她成为漫画家的梦想。她在那座寺庙里花了六个月的时间玩“翻花绳”，现在她想尝试一款不同的游戏——“蛇梯棋”。不幸的是，她已经杀死了所有的蛇，因此目前棋盘上只剩下梯子了。

该游戏在一个 $10 \times 10$ 的棋盘上进行，规则如下：

• 游戏开始时，玩家位于左下角方格。
• 游戏目标是让玩家沿路径前进并攀爬垂直梯子，最终抵达终点（即左上角方格）。一旦玩家到达终点，游戏即告结束。
• 路径规则如下：若某方格不是其所在行的末尾，则它通向该行中紧邻其右侧（或左侧）的方格；若某方格是其所在行的末尾，则它通向上一行中正上方的方格。各行的方向确定方式如下：最底行方向为向右；其余各行的方向均与它正下方那一行的方向相反。路径示意图请参见“说明”部分。
• 每回合中，玩家投掷一枚标准的六面骰子。假设骰子显示的数字为 $r$。若终点在路径上距离当前所在位置不足 $r$ 格，则玩家不移动（但该回合仍算作完成）；否则，玩家严格沿路径向前移动 $r$ 格后停止。若玩家停在某个带有梯子底部的方格上，则她可选择是否攀爬该梯子。若她选择不攀爬，则下一回合开始时她仍停留在该方格。
• 某些方格中设有梯子。所有梯子均为垂直方向——每条梯子均通往上方某一行的同一列方格。玩家只有在投骰后恰好停在某梯子底部所在的方格上，才可选择攀爬该梯子。使用梯子后，玩家将出现在该梯子顶部所在的方格。她不能在攀爬中途离开梯子。此外，若梯子顶部所在的方格同时也是一条梯子的底部，则她不允许在使用第一条梯子后继续使用第二条梯子。
• 骰子各面点数为 $1, 2, 3, 4, 5, 6$，且每个点数出现的概率均相等。

请注意：

• 梯子可能重叠，但玩家在攀爬第一条梯子中途不得切换至另一条梯子；
• 梯子可能直接通往最顶行，但不会通往更高处（即不存在超出棋盘的梯子）；
• 可能有两条或多条梯子通往同一个方格；
• 可能存在一条梯子通往一个同时作为另一条梯子底部的方格，但若玩家使用了第一条梯子，则她无法再使用第二条梯子；
• 玩家只能向上攀爬梯子，不可向下攀爬。

百谷希望尽快完成游戏。因此，她在每一回合中都会最优地决定是否攀爬梯子。请帮她计算完成游戏所需的最小期望回合数。

Input will consist of ten lines. The $i$-th line will contain 10 non-negative integers $h_{i1}, h_{i2}, \dots, h_{i10}$. If $h_{ij}$ is $0$, then the tile at the $i$-th row and $j$-th column has no ladder. Otherwise, the ladder at that tile will have a height of $h_{ij}$, i.e. climbing it will lead to the tile $h_{ij}$ rows directly above. It is guaranteed that $0 \leq h_{ij} \lt i$. Also, the first number of the first line and the first number of the last line always contain $0$, i.e. the Goal and the starting tile never have ladders.

输入包含十行。第 $i$ 行包含 10 个非负整数 $h_{i1}, h_{i2}, \dots, h_{i10}$。若 $h_{ij} = 0$，则表示第 $i$ 行、第 $j$ 列的格子上没有梯子；否则，该格子上的梯子高度为 $h_{ij}$，即攀爬该梯子将到达正上方 $h_{ij}$ 行处的格子。保证对所有 $i,j$ 均有 $0 \leq h_{ij} < i$。此外，第一行的第一个数字和最后一行的第一个数字恒为 $0$，即目标格子和起始格子上均无梯子。

Print only one line containing a single floating-point number — the minimum expected number of turns Hyakugoku can take to finish the game. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

仅输出一行，包含一个浮点数——即百国完成游戏所需的最小期望回合数。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

A visualization of the path and the board from example 2 is as follows:

The tile with an 'S' is the starting tile and the tile with an 'E' is the Goal.

For the first example, there are no ladders.

For the second example, the board looks like the one in the right part of the image (the ladders have been colored for clarity).

It is possible for ladders to overlap, as is the case with the red and yellow ladders and green and blue ladders. It is also possible for ladders to go straight to the top, as is the case with the black and blue ladders. However, it is not possible for ladders to go any higher (outside of the board). It is also possible that two ladders lead to the same tile, as is the case with the red and yellow ladders. Also, notice that the red and yellow ladders lead to the tile with the orange ladder. So if the player chooses to climb either of the red and yellow ladders, they will not be able to climb the orange ladder. Finally, notice that the green ladder passes through the starting tile of the blue ladder. The player cannot transfer from the green ladder to the blue ladder while in the middle of climbing the green ladder.

示例 2 中路径与棋盘的可视化如下：

标有 'S' 的方格为起始方格，标有 'E' 的方格为终点（目标）方格。

对于第一个示例，棋盘上没有梯子。

对于第二个示例，棋盘结构如图中右侧所示（梯子已用不同颜色标出以增强可读性）。

梯子之间可能发生重叠，例如红色梯子与黄色梯子、绿色梯子与蓝色梯子即属此类。梯子也可能直接通向棋盘顶部，例如黑色梯子与蓝色梯子即属此类。但梯子不可能延伸至棋盘之外（即无法到达比棋盘最高行更高的位置）。此外，可能存在两条（或以上）梯子通向同一方格的情况，例如红色梯子与黄色梯子均通向同一方格。还需注意，红色梯子与黄色梯子均通向标有橙色梯子的方格；因此，若玩家选择攀爬红色或黄色梯子中的任意一条，则将无法再攀爬橙色梯子。最后，请注意绿色梯子穿过蓝色梯子的起始方格；玩家在攀爬绿色梯子的过程中，不能中途转而攀爬蓝色梯子。