AT_abc293_c [ABC293C] Make Takahashi Happy

题目描述

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

现在，高桥君站在 $(1, 1)$。接下来，高桥君会反复进行“从当前格子移动到右边或下边相邻的格子”的操作，最终移动到 $(H, W)$。在移动过程中，不能移出格子范围。

如果高桥君经过的所有格子（包括起点 $(1, 1)$ 和终点 $(H, W)$）上写的整数都互不相同，那么高桥君会感到高兴。请输出作为高桥君移动路径的所有可能方案中，使高桥君高兴的方案数。

输入格式

输入以如下格式从标准输入给出。

$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}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3
3 2 2
2 1 3
1 5 4

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

48620

说明/提示

限制条件

• $2 \leq H, W \leq 10$
• $1 \leq A_{i, j} \leq 10^9$
• 输入均为整数

样例解释 1

高桥君的所有可能移动路径如下，共有 $6$ 种。

• $(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$ 种，共 $3$ 个。

样例解释 2

在这个例子中，无论高桥君选择哪条路径，他都会高兴。

由 ChatGPT 4.1 翻译