SP19146 INS14E - Glorious Gamblers

2012年，Digo 和 Tourist 在为 CIA 任务培训的过程中成为了好朋友。Digo 是个怀疑论者，相信当年世界会终结，而 Tourist 则认为这毫无道理。在多次争论无果后，他们决定打赌，然后继续训练。 到了2014年，他们在首次任务中再次相遇。很显然，Digo 的预言错了，现在是他兑现赌注的时候。由于两人都是优秀的程序员，他们决定通过一个游戏来解决赌注问题。Digo 应支付给 Tourist 的金额可以用一个 \( M \times N \) 的矩阵 \( A \) 来表示，其中每个元素都是正整数。 游戏规则是这样的：他们在矩阵的起点 (1,1) 放置一个环，游戏在环到达终点 (M,N) 时结束。当环在位置 (i,j) 时，他们抛一枚公平硬币。若是正面朝上，则 Digo 移动环；若是反面朝上，则 Tourist 移动环。在每一次移动中，环可以从当前位置 (i,j) 移动到东方、南方或东南方的相邻单元格，且无法移出矩阵的边界。 在整个移动过程中，Digo 走过路径上的每个单元格数值总和便是他需支付给 Tourist 的金额。Digo 希望通过努力最小化这一总和，而 Tourist 则希望最大化这一数值。 请帮 Digo 计算在游戏结束时，他需支付给 Tourist 的期望金额，并要精确到小数点后6位。 注意：输入量较大，请使用快速的I/O方法。

第一行包含一个整数 \( T \)，表示测试用例的数量。 对于每个测试用例： - 第一行包括两个整数 \( M \) 和 \( N \)，表示矩阵的尺寸。 - 接下来的 \( M \) 行中，每行包含 \( N \) 个整数，表示矩阵 \( A \) 的元素值。

对于每个测试用例，输出一个结果，即Digo在游戏结束时需支付给Tourist的期望金额，精确到小数点后6位。

- \( 1 \leq T \leq 10 \) - \( 2 \leq M, N \leq 500 \) - \( 0 \leq A[i][j] \leq 10^6 \) ## 样例输入 ``` 1 2 3 1 2 2 3 5 1 ``` ## 样例输出 ``` 8.250000 ``` **本翻译由 AI 自动生成**