P1187题解

TIS_Minecraft_CNAI · 2023-10-17 00:11:29 · 个人记录

P1187题解

这是本蒟蒻第一次写题解，求管理员通过

P1.先讲思路：

首先，我们将四周一圈设为 0 ，即高度为 0 的建筑。

先定义一个二维数组 a，a[i][i] 表示第 i 行第 j 列的建筑高度。

显然，只要高度不为 0，它的表面积就至少是 2。

我们可以把每个建筑分为 a[i][j] 层，每层高度为 1，然后逐层向四个方向搜索，如果它四周的建筑高度不比它低，就说明这面没有被遮挡，临时变量 sum 加一。四个方向搜完后就把临时变量 sum 加到总数 ans 里，零时变量清零。

P2.代码分解：

1. 定义：

   • n，m，ans，a[1005][10005]
   • 方向数组：x[5]= {0,0,0,1,-1}，y[5]= {0,1,-1,0,0}

2. 输入：

   因为题目输入的时候没有空格，我们可以定义一个字符变量，每次输入一个字符，然后把它转存到 a 数组里去

   cin>>n>>m;
   for(int i=1; i<=n; i++)
       for(int j=1; j<=m; j++) {
           char c;
           cin>>c;
           a[i][j]=c-'0';
       }

3. 主体：查找

   思路已经说过了，大体就是遍历整个 a 数组，想 P1 里说的那样查找，时间复杂度是 O(36nm)

   for(int i=1; i<=n; i++)
       for(int j=1; j<=m; j++) {
           if(a[i][j]==0)
               continue;
               ans+=2;
               for(int h=1; h<=a[i][j]; h++) {
                   int sum=0;
                   for(int k=1; k<=4; k++) {
                       int dx=i+x[k];
                       int dy=j+y[k];
                       if(a[dx][dy]<h)
                           sum++;
                   }
                   ans+=sum;
               }
       }

P4.整体代码：

using namespace std;
int n,m,a[1005][1005];
int x[5]= {0,0,0,1,-1};
int y[5]= {0,1,-1,0,0};     //方向数组
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }     //输入
    int ans=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            if(a[i][j]==0)
                continue;     //如果高度为0，直接跳过
            ans+=2;     //高度不为0，ans++
            for(int h=1; h<=a[i][j]; h++) {     //从一开始枚举高度
                int sum=0;     //临时变量，记录每层的表面积
                for(int k=1; k<=4; k++) {     //四个方向
                    int dx=i+x[k];
                    int dy=j+y[k];
                    if(a[dx][dy]<h)
                        sum++;     //如果它四周的建筑高度不比它低,说明这面没有被遮挡，sum++
                }
                ans+=sum;     //把临时变量加到总数里去
            }
        }
    cout<<ans;     //输出答案
    return 0;     //拜拜~~~
}