NSOqwq

题解 P7479【至曾是英雄的您】

题目大意

给你一个棋盘,棋盘里有一块连通的黑棋。要你在它的周围下白棋,但下的每一步白棋必须满足:

  • 这个白棋下完以后所在的白棋连通块至少有一口气;

  • 这个白棋下完以后黑棋已没有气。

如果最终能使黑棋没有气,输出 NO;否则输出 YES


思路

以样例 3 为例。遍历每一个没有棋子的连通块。

图 2 是包围黑子所必须下的白棋。

图 1 是所有的没有棋子的连通块。

显然,左上角的红色连通块必须要放满白棋,中间的绿色连通块只用放四个角的四个就行,中间的那个格子不用。在蓝色连通块中,最右上角的那个格子也不用放白棋。

那么我们的下棋顺序可以是:绿色连通块的四个 → 蓝色连通块的三个 → 红色连通块。当红色连通块的最后一个棋子下完以后,虽然红色连通块没有气了,但黑棋也没有气了。是合法的。

当然,也可以蓝 → 绿 → 红,因为蓝和绿不用下满,无论怎么下,它上面的白棋至少有一口气可以呼吸。但红必须最后一个下。


总结:

当一个连通块必须被下满的时候,它必须得放在最后一个下。

所以,当必须下满的连通块大于 1 个时,黑棋无法被包围,它是“活棋”。

否则,它不是“活棋”。


做法

遍历每一个没有棋子的连通块,然后对于每一个连通块,遍历它的每一个点。如果这个点与黑棋相邻,则标记这个点。最终,如果被标记的点的个数与连通块中点的总数相等(即这个连通块需要得被下满),则标记这个连通块。如果最终被标记的连通块总数大于 1,则输出 YES,否则输出 NO。

查找连通块可以用并查集实现;剩下的只需要模拟即可。

我的做法是超大常数的,使用了 vector + set,不开 O2 会 T 掉 6 个点。于是愉快地换成手写的 vector,过了。


Code

手写 Vec 部分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

// 手写 vector 部分见链接

const int N = 2001;
int n, m;
char map[N][N];
int father[N * N];
NSO::Vector<int> buck[N * N];
std::set<int> qwq;
int dX[4] = {0, 1, 0, -1};
int dY[4] = {1, 0, -1, 0};
inline int read() {
    int t = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { ch = getchar(); }
    do { t = t * 10 + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
    return t;
}
inline char readChar() {
    char ch = getchar();
    while (ch != '*' && ch != '.') ch = getchar();
    return ch;
}
void init() {
    qwq = std::set<int>();
    for (register int i = 1; i <= n * m + 2; ++i)
        father[i] = i, buck[i] = NSO::Vector<int>();
}
int findFather(int x) {
    if (father[x] == -1)
        return -1;
    if (father[x] != x) {
        father[x] = findFather(father[x]);
    }
    return father[x];
}
void merge(int r1, int r2) {
    r1 = findFather(r1);
    r2 = findFather(r2);
    if (findFather(r1) != findFather(r2))
        father[r1] = r2;
}
bool isRelative(int r1, int r2) {
    return findFather(r1) == findFather(r2);
}
int convert(int x, int y) { // 并查集实现部分我将一个坐标编码为了一个整数,即 (行号 - 1) * 总列数 + 列号
    return (x - 1) * m + y;
}
void mian() {
    n = read(), m = read();
    init();

    // 读入
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j) {
            map[i][j] = readChar();
            if (map[i][j] == '*')
                father[ convert(i, j) ] = -1; // 不需要判黑棋连通块,所以全给 -1
        }

    // 并查集
    for (register int i = 1; i <= n; ++i) {
        for (register int j = 1; j <= m; ++j) {
            for (register int k = 0; k < 4; ++k) {
                int newX = i + dX[k];
                int newY = j + dY[k];

                if (newX >= 1 && newY >= 1 && newX <= n && newY <= m) {
                    if (map[newX][newY] == '.' && map[i][j] == '.') { // 合并
                        merge(convert(newX, newY), convert(i, j));
                    }
                }
            }
        }
    }

    // 找连通块
    for (register int i = 1; i <= n * m; ++i) {
        if (father[i] != -1) {
            buck[findFather(i)].push_back(i); // buck[i] 里装连通块编号为 i 的所有位置编号
            qwq.insert(findFather(i)); // 一个 set 记录所有的连通块编号
        }
    }

    // 遍历
    int qaq = 0;

    // 遍历每一个联通块
    for (int item : qwq) {
        int count = 0;

        for (register int i = 0; i < buck[item].size(); ++i) { // 遍历一个联通块中每一个点(手写 Vector 无法用 C++11(悲))
            int pos = buck[item][i];
            int y = (pos % m) == 0 ? m : pos % m;
            int x = (pos - y) / m + 1; // 解码成坐标
            for (register int k = 0; k < 4; ++k) {
                int newX = x + dX[k];
                int newY = y + dY[k];

                if (newX >= 1 && newY >= 1 && newX <= n && newY <= m) {
                    if (map[newX][newY] == '*') { // 如果与黑棋子相邻
                        ++count;
                        break;
                    }
                }
            }
        }
        if (count >= buck[item].size())
            ++qaq;
    }
    if (qaq >= 2) fputs("YES\n", stdout);
    else fputs("NO\n", stdout);
}
// 【main 函数已被隐藏】

2021-04-05 17:53:14 in 未分类