DDOSvoid's Blog

CF 1536E Omkar and Forest

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/1536/E

简要题意：给定一个 $n\times m$ 的仅包含0 #的网格，现在需要向网格上的每个位置分配一个非负整数，我们认为一种分配方案是合法的，当且仅当满足对于任意两个相邻的格子，这两个格子中的数的绝对值不超过1和如果一个格子中的数为正整数，那么与这个格子相邻的四个格子中至少有一个格子里的数比这个格子小，现在我们强制 $0$ 网格中的数字为 $0$​，请问有多少种合法分配方案

$n,m\le 2000$

Solution

我们不妨强制令某些#位置的数字为 $0$，然后我们考虑这样一种分配方案，每个位置的数字是离他最近的 $0$ 的距离

根据最短路的性质，容易得到这样一定满足条件 $1$，我们现在给出一个结论为确定 $0$ 的位置后，整张图的数字都确定了，且这唯一的分配方案就是我们之前提到的分配方案

首先，对于任何一个位置 $p$，如果我们将其加 $1$，容易得到在求最短路过程中，更新 $p$ 的最短路的那个点将于 $p$ 的差值大于 $1$，这样会不符合条件 $1$

对于任何一个位置 $p$，如果我们将其减 $1$，容易得到它的周围将不存在比它小的点

我们令 $cnt$ 表示#的数量，容易得到答案就是 $2^{cnt}-[cnt=nm]$

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
#include <iostream>
#define maxn 2010
#define ll long long 
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int n, m;
char s[maxn];

void work() {
    cin >> n >> m; int ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> s + 1;
        for (int j = 1; j <= m; ++j) ans += s[j] == '#';
    } cout << pow_mod(2, ans) - (ans == n * m) << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; 
    while (T--) work(); 
    return 0; 
}