P16099 [ICPC 2019 NAIPC] Monotony

给定一个 $r \times c$ 的网格。网格的每个格子都填有一个 $1$ 到 $r \cdot c$ 之间的整数，且所有格子中的数互不相同。 如果一个网格的每一行和每一列都是单调递增或单调递减的（不同行或不同列的单调方向可以不同），则称该网格为 **单调网格**。 按下述方式定义网格的一个 **子网格**：首先选择若干行和若干列（均非空）。然后，取出这些选定行和选定列所对应的元素，并保持原有的顺序。 给定网格共有 $(2^r - 1)(2^c - 1)$ 个非空子网格。请统计其中有多少个子网格是单调的。 考虑如下网格： $$ \begin{array}{} 1 & 2 & 5\\ 7 & 6 & 4\\ 9 & 8 & 3 \end{array} $$ 它有 9 个 $1 \times 1$ 子网格、9 个 $1 \times 2$ 子网格、3 个 $1 \times 3$ 子网格、9 个 $2 \times 1$ 子网格、9 个 $2 \times 2$ 子网格、3 个 $2 \times 3$ 子网格、3 个 $3 \times 1$ 子网格、3 个 $3 \times 2$ 子网格和 1 个 $3 \times 3$ 子网格。所有这些子网格都是单调的，因此单调子网格的总数为 $9 + 9 + 3 + 9 + 9 + 3 + 3 + 3 + 1 = 49$。

每个测试用例的第一行包含两个空格分隔的整数 $r$ 和 $c$（$1 \leq r, c \leq 20$），表示网格的尺寸。 接下来的 $r$ 行，每行包含 $c$ 个空格分隔的整数 $x$（$1 \leq x \leq r \cdot c$，所有 $x$ 互不相同），表示网格。

输出一个整数，表示给定网格中单调子网格的数量。

翻译由 DeepSeek V3.2 完成