题解：P8217 [THUPC 2022 初赛] 数正方体

· · 题解

你们所有人都没想到的方法

这个题目已经不接受新题解了，那么我可以放开文章的格式了

这个方法比较简单：开始置ans变量为0，多次遍历整张图，每当识别到图中有如下正方体结构时

..+---+
./   /|
+---+ |
|   | +
|   |/.
+---+..

ans+=1，且直接改动原图，将其修改为

..+---+
./|   |
+ |   |
| +   +
|/   /.
+---+..

重复如上步骤，使得图中不存在正方体结构为止

可能你们没看懂上面的内容是什么意思。等会我给一个例子

例子

对于如下的图

..+---+---+
./   /   /|
+---+---+ |
|   |   | +
|   |   |/.
+---+---+..

我们知道它有两个正方体。如果使用上面的算法，它的过程如下。首先第一次遍历它会识别到在坐标[4:10][0:6]之间有一个正方体结构

..+---#####
./   #   ##
+---##### #
|   #   # #
|   #   ##.
+---#####.

其中右面的正方体因为三个面都显露在外面，于是可以识别到它的正方体结构；而左面的正方体因为只有两个面在外面，无法识别到它的正方体结构

然后自加ans为1，将原图修改为

..+---+---+
./   /|   |
+---+ |   |
|   | +---+
|   |/   /.
+---+---+..

再次遍历整张图，发现图中仍然有一个正方体结构。

此时图中已经删去右面的正方体，左面的正方体的三个面都显露在外面

于是再次自加ans，并将图修改为

..+---+---+
./|   |   |
+ |   |   |
| +---+---+
|/   /   /.
+---+---+..

此时图中没有正方体。于是输出ans，此时它的值为2

代码复杂度

时间复杂度O(m+n+max{A_{i,j}}) 空间复杂度O(m*n*max{A_{i, j}})

代码实现

#include <cstdio>
#include <cstdlib>

char mp[500][500];

bool check(int i, int j){
    static const char mod[][100] = {
        "..+---+",
        "./   /|",
        "+---+ |",
        "|   | +",
        "|   |/.",
        "+---+.."
    };
    for (int k=0; k<6; k++){
        for (int l=0; l<7; l++){
            if (mod[k][l]=='.'){
                continue;
            }
            if (mp[i+k][j+l]==mod[k][l]){
                continue;
            } else {
                return false;
            }
        }
    }
    return true;
}

void edit(int i, int j){
    static const char mod[][100] = {
        "..+---+",
        "./|   |",
        "+ |   |",
        "| +---+",
        "|/   /.",
        "+---+.."
    };
    for (int k=0; k<6; k++){
        for (int l=0; l<7; l++){
            if (mod[k][l]=='.'){
                continue;
            }
            mp[i+k][j+l] = mod[k][l];
        }
    }
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            char c;
            do{
                c = getchar();
            } while (c=='\n');
            mp[i][j] = c;
        }
    }
    int ans=0;
    bool ok = true;
    while (ok){
        ok = false;
        for (int i=0; i<490; i++){
            for (int j=0; j<490; j++){
                if (check(i, j)){
                    ans++;
                    ok = true;
                    edit(i, j);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}