P8217 [THUPC2022 初赛] 数正方体 官方题解

· · 题解

看了一下大家的题解，这里出题人还是写一下最简单的官方题解吧。

首先 n 和 m 可以通过输入的最后一行得出。由于 A_{ij}>0，最后一行一定是一堆非 . 字符加上一堆 . 组成，其中非 . 字符的个数是 4m+1，. 的个数是 2n。

得到 n 和 m 以后考虑计算每一列有多少个正方体。这个值可以通过顶面高度减去底面高度的差（或者说底面行号减去顶面行号）除以 3 得到。甚至我们不必考虑哪个顶面和哪个底面对应，我们只需要求出所有顶面的行号和和所有底面的行号和就可以了。

由于顶面不会被遮挡，我们可以用字符串 / /（两个斜杠之间三个空格）匹配顶面。这样顶面的行号和就能求了。

底面呢？在 r-1,r-3,r-5,\cdots,r-2n+1 行均分别有 m 个底面，所以所有底面的行号和为 m\sum\limits_{i=1}^n(r-2i+1)=mn(r-n)。

匹配顶面可以用 strstr 函数。然后这题就做完了。不需要任何的 DFS 或者 Check 函数。

代码：

#include<bits/stdc++.h>
char map[555][444];
int main()
{
    int r,c;
    scanf("%d%d\n",&r,&c);
    for(int i=1;i<=r;++i,getchar())
        for(int j=1;j<=c;++j)
            map[i][j]=getchar();               //输入
    int p=strstr(map[r]+1,".")-map[r];
    int m=p-2>>2,n=c-p+1>>1;                           //计算m和n
    int ans=m*n*(r-n);                                 //计算底面行号和
    for(int i=2;i<=r;++i)
    {
        int now=1;
        char* tmp;
        while(tmp=strstr(map[i]+now,"/   /"))
            ans-=i,now=tmp-map[i]+4;           //计算每行有多少个顶面
    }
    printf("%d\n",ans/3);
    return 0;
}