当前没有测试数据。

C - 让Takahashi开心

得分：$300$ 分

问题描述

有一个 $H$ 行 $W$ 列的网格。 对于两个整数 $i$ 和 $j$，满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$， 第 $i$ 行从上到下数第 $j$ 列（记作 $(i, j)$）上有一个整数 $A_{i, j}$。

Takahashi 目前在 $(1,1)$ 处。 从现在开始，他重复向着右边或者下边一个相邻的方块移动，直到达到 $(H, W)$ 处。 在移动时，他不能离开网格。

如果他经过的方块上的整数（包括起始点 $(1, 1)$ 和终点 $(H, W)$）互不相同，那么 Takahashi 会开心。 你需要找出可以使 Takahashi 开心的路径的数量。

约束

• $2 \leq H, W \leq 10$
• $1 \leq A_{i, j} \leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入中读取以下格式的输入：

$H$ $W$

$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$

$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$

$\vdots$

$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

输出

输出答案。

3 3
3 2 2
2 1 3
1 5 4

3

有六个可能的路径：

• $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 2, 3, 4$，因此他不会开心。
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 1, 3, 4$，因此他不会开心。
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 1, 5, 4$，因此他会开心。
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 1, 3, 4$，因此他不会开心。
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 1, 5, 4$，因此他会开心。
• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$：经过的方块上的整数是 $3, 2, 1, 5, 4$，因此他会开心。

所以，上述的第三、第五和第六条路径会使他开心。

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

48620

在这个例子中，所有可能的路径都会使他开心。