题解 CF750H 【New Year and Snowy Grid】

_sys · 2020-10-19 09:51:08 · 题解

我们考虑，若询问的是 (1, 1) 与 (h, w) 是否连通，该如何解决。

不难发现，我们若在网格外加一层 #，则 (1, 1) 与 (h, w) 通过 . 四连通当且仅当 (h + 1, 0) 与 (0, w + 1) 通过 # 无法八连通。

如图，蓝色为网格外加的一层 #，此时 # 八连通，所以 . 无法四连通。

同理，我们可以得出，. 双四连通（存在两条不交的四连通路径）当且仅当 # 无法“几乎”八连通。“几乎”八连通指的是存在一种方案使得仅添加一个 # 即可八连通。

如图，S 到 E 仅存在一条路径，所以黑色是“几乎”八连通的。

那么我们现在的问题变为，添加 k 个 # 后，如何判定 # 是否“几乎”八连通。

我们考虑首先对于每个连通块，求出已经“几乎”八连通的连通块邻居，即使它们有可能还没有和左下右上连通。在网格上走至多两步走到的连通块都是。

我们把可能 No 的情况分为两种：

两个新的 # 切比雪夫距离 \leq 2，并且它们一个和左下连通，一个和右上连通。
一些新的 # 使得一些原来孤立的连通块和左下连通了，而这个连通块又有“几乎”八连通的邻居现在和右上连通。

第一种情况 k^2 枚举即可。

第二种情况，我们发现这样的连通块至多只有 O(dk) 种，其中 d=8 表示一个格子的相邻格子数，枚举每个连通块的“几乎”八连通邻居，看看是否和右上连通。最多 O(d^2) 种，总复杂度 O(d^3k)。

实现上我用了可撤销并查集。

注意空间限制只有 256MB，不要放飞自我。

时间复杂度：O(hwd^2+qd^3k)。

代码：

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 1005, Maxc = 2000005;
const int dx[] = {0, -1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {0, -1, 0, 1, 1, 1, 0, -1, -1};
int h, w, q, ct, dsu_ct, u[15], v[15], id[Maxn][Maxn], fa[Maxc], siz[Maxc], tmp_fa[Maxc], tmp_siz[Maxc];
char G[Maxn][Maxn];
set <int> Se[Maxc];
pair <int, int> D[Maxc];
int get_fa(int x)
{
    return x == fa[x] ? x : fa[x] = get_fa(fa[x]);
}
void merge(int x, int y)
{
    int a = get_fa(x), b = get_fa(y);
    fa[a] = b;
    if (a != b) siz[b] += siz[a];
}
int tmp_get_fa(int x)
{
    return x == tmp_fa[x] ? x : tmp_get_fa(tmp_fa[x]);
}
void tmp_merge(int x, int y)
{
    int a = tmp_get_fa(x), b = tmp_get_fa(y);
    if (a == b) return ;
    if (tmp_siz[a] > tmp_siz[b]) swap(a, b);
    D[++dsu_ct] = make_pair(a, b);
    tmp_fa[a] = b;
    tmp_siz[b] += tmp_siz[a];
}
void dfs(int x, int y, int c, set <int> &S)
{
    if (x == 2 && y == 2) return ;
    if (x == h - 1 && y == w - 1) return ;
    if (G[x][y] == '#') S.insert(get_fa(id[x][y]));
    if (!c) return ;
    for (int d = 1; d <= 8; d++)
        if (id[x + dx[d]][y + dy[d]]) dfs(x + dx[d], y + dy[d], c - 1, S);
}
int main()
{
    scanf("%d%d%d", &h, &w, &q);
    h += 2, w += 2;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            id[i][j] = ++ct, fa[ct] = ct, siz[ct] = 1;
    for (int i = 3; i <= h; i++)
        G[i][1] = '#';
    for (int i = 1; i <= h - 3; i++)
        G[i][w] = '#';
    for (int i = 3; i <= w; i++)
        G[1][i] = '#';
    for (int i = 1; i <= w - 3; i++)
        G[h][i] = '#';
    for (int i = 2; i <= h - 1; i++)
        for (int j = 2; j <= w - 1; j++)
        {
            G[i][j] = getchar();
            while (G[i][j] != '.' && G[i][j] != '#') G[i][j] = getchar();
        }
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            for (int d = 1; d <= 8; d++)
                if (id[i + dx[d]][j + dy[d]] && G[i][j] == '#' && G[i + dx[d]][j + dy[d]] == '#')
                    merge(id[i][j], id[i + dx[d]][j + dy[d]]);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            dfs(i, j, 2, Se[get_fa(id[i][j])]);
    memcpy(tmp_fa, fa, sizeof(int[ct + 1]));
    memcpy(tmp_siz, siz, sizeof(int[ct + 1]));
    while (q--)
    {
        dsu_ct = 0;
        int k;
        scanf("%d", &k);
        for (int i = 1; i <= k; i++)
        {
            scanf("%d%d", &u[i], &v[i]);
            u[i]++, v[i]++;
            G[u[i]][v[i]] = '#';
        }
        for (int i = 1; i <= k; i++)
            for (int d = 1; d <= 8; d++)
                if (id[u[i] + dx[d]][v[i] + dy[d]] && G[u[i] + dx[d]][v[i] + dy[d]] == '#')
                    tmp_merge(id[u[i]][v[i]], id[u[i] + dx[d]][v[i] + dy[d]]); 
        for (int i = 1; i <= k; i++)
            for (int d = 0; d <= 8; d++)
                if (id[u[i] + dx[d]][v[i] + dy[d]])
                {
                    if (tmp_get_fa(id[u[i] + dx[d]][v[i] + dy[d]]) == tmp_get_fa(id[h][1]))
                    {
                        int pos = get_fa(id[u[i] + dx[d]][v[i] + dy[d]]);
                        for (set <int> :: iterator it = Se[pos].begin(); it != Se[pos].end(); it++)
                            if (tmp_get_fa(*it) == tmp_get_fa(id[1][w]))
                            {
                                puts("NO");
                                goto END;
                            }
                    }
                    if (tmp_get_fa(id[u[i] + dx[d]][v[i] + dy[d]]) == tmp_get_fa(id[1][w]))
                    {
                        int pos = get_fa(id[u[i] + dx[d]][v[i] + dy[d]]);
                        for (set <int> :: iterator it = Se[pos].begin(); it != Se[pos].end(); it++)
                            if (tmp_get_fa(*it) == tmp_get_fa(id[h][1]))
                            {
                                puts("NO");
                                goto END;
                            }
                    }
                }
        for (int i = 1; i <= k; i++)
            for (int j = i + 1; j <= k; j++)
                if (max(abs(u[i] - u[j]), abs(v[i] - v[j])) <= 2)
                {
                    if (tmp_get_fa(id[u[i]][v[i]]) == tmp_get_fa(id[1][w]) && tmp_get_fa(id[u[j]][v[j]]) == tmp_get_fa(id[h][1]))
                    {
                        puts("NO");
                        goto END;
                    }
                    if (tmp_get_fa(id[u[i]][v[i]]) == tmp_get_fa(id[h][1]) && tmp_get_fa(id[u[j]][v[j]]) == tmp_get_fa(id[1][w]))
                    {
                        puts("NO");
                        goto END;
                    }
                }
        puts("YES");
        END:fflush(stdout);
        for (int i = dsu_ct; i >= 1; i--)
        {
            tmp_fa[D[i].first] = D[i].first;
            tmp_siz[D[i].second] -= tmp_siz[D[i].first];
        }
        for (int i = 1; i <= k; i++)
            G[u[i]][v[i]] = '.';
    }
    return 0;
}