#P6473. [thoi2012]水位
[thoi2012]水位
题目描述
给定一个 的方格地区。每个格子的地表高度是一个 到 的整数。地区四周的边界无限高。
每个格子要么无水,要么有一个统一的水面高度。水面高度是 到 的整数,且有水格子的水面高度严格高于该格的地表高度。
共边相邻的两个格子必须符合以下规则。
- 若两个格子都有水,它们的水面高度必须相同。
- 若一个格子有水,另一个无水,有水格子的水面高度不能高于无水格子的地表高度。
- 两个格子都无水时没有额外限制。
求满足这些规则的水位方案数。只要某个格子的有水状态或水面高度不同,便视为不同方案。
输入格式
第一行两个正整数 。接下来 行,每行 个非负整数,表示对应格子的地表高度。
输出格式
输出一个整数,表示方案数。
样例
4 3
1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 2
6
除了右下角的独立格子,其余格子可以完全不积水、按规则积水到高度 ,或按规则积水到高度 。右下角格子在这三种情况下均可独立选择无水或积水到高度 。
数据范围
| 测试点 | 上界 | 上界 |
|---|---|---|
| 1–2 | 5 | 5 |
| 3–4 | 30 | |
| 5–6 | 10 | 5 |
| 7–8 | 30 | |
| 9–12 | 30 | 1000 |
| 13–14 | ||
| 15–16 | 100 | 1000 |
| 17–20 |