Make Takahashi Happy

题目描述

有一个由 $H$) 行水平方向和 $W$ 列垂直方向组成的网格。 对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数 $i$ 和 $j$， 位于自上数第 $i$ 行自左数第 $j$ 列的方格（记为 $(i, j)$）上写有一个整数 $A_{i, j}$。 Takahashi 目前位于 $(1,1)$。 从现在起，他重复向右或向下移动到相邻的方格，直到到达 $(H, W)$。 当他移动时，不允许他离开网格。 如果他访问的方格上写的整数（包括起始的 $(1, 1)$ 和终点 $(H, W)$）互不相同，Takahashi 会感到高兴。 求使他感到高兴的可能路径数。

输入格式

输入从标准输入按以下格式给出： $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

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

提示

$2 \leq H, W \leq 10$ $1 \leq A_{i, j} \leq 10^9$ 输入中的所有数值均为整数。共有六条可能的路径：

$(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$，因此他 会 感到高兴。

因此，上述第 3、5、6 条路径会使他感到高兴。
在这个例子中，每一条可能的路径都使他感到高兴。

标签: AtCoder|abc293C

来源

AtCoder|abc293C