← 返回题目列表

AtCoder · jag2017summer_day3_e

E. 路线计算器

中文机器翻译题面 查看原题

问题陈述

您有一个包含 $H$ 行和 $W$ 列的网格。 $H+W$ 是偶数。我们用 $(i, j)$ 表示从顶部算起第 $i$ 行和从左边算起第 $j$ 列的单元格。在任何单元格 $(i, j)$ 中,如果 $i+j$ 为偶数,则写入 $1$ 和 $9$ 之间的整数,并且 如果 $i+j$ 为奇数,则写入 + or * 。

您可以通过从 $(1,1)$ 到 $(H,W)$ 向右或向下移动 $H+W-2$ 次并按顺序连接您传递的单元格中写入的所有字符来获得数学表达式。您的任务是通过选择从 $(1, 1)$ 到 $(H, W)$ 的任意路径来最大化所得数学表达式的计算值。如果最大值为 $10^{15}$ 或更小,则打印该值。否则,打印 $-1$。


输入

输入由以下格式的单个测试用例组成。

$H$ $W$ $a_{1,1}$ $\cdots$ $a_{1,W}$ $\l点$ $a_{H,1}$ $\cdots$ $a_{H,W}$

第一行由两个整数 $H$ 和 $W$ ($1 \le H,W \le 50$) 组成。保证$H+W$是偶数。 以下 $H$ 行代表网格上的字符。 $a_{i,j}$ 表示单元格$(i,j)$ 中写入的字符。在任何单元格 $(i, j)$ 中,如果 $i+j$ 为偶数,则写入 $1$ 和 $9$ 之间的整数,并且 + or * 。

输出

在一行中打印答案。


示例输入 1

3 3
1+2
+9*
1*5

样本输入 1 的输出

46

通过传递以下单元格获得最大值:$(1,1)$、$(2,1)$、$(2,2)$、$(2,3)$、$(3,3)$。


示例输入 2

1 31
9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9

样本输入 2 的输出

-1

你可以获得$9^{16}$,但它太大了。


示例输入 3

5 5
2+2+1
+1+1+
1+2+2
+1+1+
1+1+2

样本输入 3 的输出

10

示例输入 4

9 7
8+9*4*8
*5*2+3+
1*3*2*2
*5*1+9+
1+2*2*2
*3*6*2*
7*7+6*5
*5+7*2+
3+3*6+8

样本输入 4 的输出

86408