#P6473. [thoi2012]水位

    ID: 5067 传统题 1000ms 256MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-事件排序普通并查集树形 DP高精度加法高精度乘法

[thoi2012]水位

题目描述

给定一个 N×NN\times N 的方格地区。每个格子的地表高度是一个 00 到 MM 的整数。地区四周的边界无限高。

每个格子要么无水,要么有一个统一的水面高度。水面高度是 00 到 MM 的整数,且有水格子的水面高度严格高于该格的地表高度。

共边相邻的两个格子必须符合以下规则。

  • 若两个格子都有水,它们的水面高度必须相同。
  • 若一个格子有水,另一个无水,有水格子的水面高度不能高于无水格子的地表高度。
  • 两个格子都无水时没有额外限制。

求满足这些规则的水位方案数。只要某个格子的有水状态或水面高度不同,便视为不同方案。

输入格式

第一行两个正整数 N,MN,M。接下来 NN 行,每行 NN 个非负整数,表示对应格子的地表高度。

输出格式

输出一个整数,表示方案数。

样例

4 3
1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 2
6

除了右下角的独立格子,其余格子可以完全不积水、按规则积水到高度 22,或按规则积水到高度 33。右下角格子在这三种情况下均可独立选择无水或积水到高度 33。

数据范围

测试点 NN 上界 MM 上界
1–2 5 5
3–4 30
5–6 10 5
7–8 30
9–12 30 1000
13–14 10910^9
15–16 100 1000
17–20 10910^9

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页