Minecraft我的世界(矩阵处理)- HDU 5538

Problem Description

Have you ever played the video game Minecraft? This game has been one of the world's most popular game in recent years. The world of Minecraft is made up of lots of 1×1×1 blocks in a 3D map. Blocks are the basic units of structure in Minecraft, there are many types of blocks. A block can either be a clay, dirt, water, wood, air, ... or even a building material such as brick or concrete in this game.

玩过Minecraft我的世界?这个游戏是近年来世界上最流行的游戏。Minecraft的世界是由小方块(1x1x1)构成,有很多类型的小方块,有些小方块是黏土、水、木材、空气,有些是小砖块、混泥土。

Figure 1: A typical world in Minecraft. Nyanko-san is one of the diehard fans of the game, what he loves most is to build monumental houses in the world of the game. One day, he found a flat ground in some place. Yes, a super flat ground without any roughness, it's really a lovely place to build houses on it. Nyanko-san decided to build on a n×m big flat ground, so he drew a blueprint of his house, and found some building materials to build.

Nyanko是这个游戏的铁粉,他最喜欢做的事情就是建大房子。一天,他发现了一个平坦的陆地,这是一个超级大的平地,在这里建造房子实在是再好不过了。Nyanko决定建造一个nxm大小的平地,他绘制了房子的蓝图,并且找到了一些建造材料。

While everything seems goes smoothly, something wrong happened. Nyanko-san found out he had forgotten to prepare glass elements, which is a important element to decorate his house. Now Nyanko-san gives you his blueprint of house and asking for your help. Your job is quite easy, collecting a sufficient number of the glass unit for building his house. But first, you have to calculate how many units of glass should be collected.

当一切顺利安排后,有一个小问题。Nyanko发现他忘了放置玻璃方块,这是装饰用的。Nyanko于是带着蓝图来找你让你想想办法。你的任务很简单,收集足够多的玻璃方块去建造他的房子。在做之前,你需要计算一下到底需要多少玻璃方块才能满足需求。

There are n rows and m columns on the ground, an intersection of a row and a column is a 1×1 square,and a square is a valid place for players to put blocks on. And to simplify this problem, Nynako-san's blueprint can be represented as an integer array ci,j(1≤i≤n,1≤j≤m). Which ci,j indicates the height of his house on the square of i-th row and j-th column. The number of glass unit that you need to collect is equal to the surface area of Nyanko-san's house(exclude the face adjacent to the ground).

陆地是一个n行m列的平面,行列之间是1x1大小的方形。为了简单起见,Nyanko的图纸可以表示成一个二维数组Cij,其中i大于1小于n,j大于1小于m,Cij表示的是i行j列的高度,玻璃方块的数量就是房子的体积。(注意是3D的,看文字不好理解,可以参考下面的图片)

Input

The first line contains an integer T indicating the total number of test cases. First line of each test case is a line with two integers n,m. The n lines that follow describe the array of Nyanko-san's blueprint, the i-th of these lines has m integers ci,1,ci,2,...,ci,m, separated by a single space.

第一行数字表示测试用例个数。

每个测试用例的第一行有两个数字n和m。

接下来n行表示数组,Nyanko的图纸的m列个数字 1≤T≤50 1≤n,m≤50 0≤ci,j≤1000

Output

For each test case, please output the number of glass units you need to collect to meet Nyanko-san's requirement in one line.

Sample Input

2
3 3
1 0 0
3 1 2
1 1 0
3 3
1 0 1
0 0 0
1 0 1

Sample Output

30 20 

Figure 2: A top view and side view image for sample test case 1.

(小编注:郭大仙初来乍到~

新手上路,先带来一道水题练练手感。

题目copy老是出错,我就直接贴题意吧:

输入数据例数T;

接下来T例输入地图大小m*n和地图每个格子上的方块数;

要求输出每个地图的表面积(不包括底面积)。

思路:

因为每个方块是叠上去的,所以不用担心会出现有空心立方体、平放杯子或者倒金字塔这些奇葩的情况。

上表面积很简单,无非就是当格子放有方块(即方块数!=0)时,上表面积+1,否则不变.

接下来我们讨论侧面积,不妨假设有高度为A和高度为B的两垒方块相邻放置,那么它们靠着的面有一部分不再是表面积了,而另一部分 |A-B| 则是一部分侧面积。因此,我们不难求出所有的侧面积——从第一行开始,每次算每个格子的右、下两个侧面积 。

但不少人会对第一列(行)或最后一列(行)作一个特判,其实完全不必如此。这样做不仅使代码长度增加,更会增加运行时间。我们只需要把四周置为0,作一个通判,不仅代码减短,还能减少时间,以下是15ms的一串代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int maze[55][55];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m,n,ans=0;
        cin>>m>>n;
        //!!!每次都要对地图清零
        memset(maze,0,sizeof(maze));   
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&maze[i][j]);
            }
        }
        for(int i=0;i<=m;i++)
        {
            //i、j从0开始,可以免去对第一列(行)的特判
            for(int j=0;j<=n;j++)
            {
                //加上maze[i][j]这个方块的下侧表面积
                ans+=abs(maze[i][j]-maze[i+1][j]);
                //加上本方块的右侧面积
                ans+=abs(maze[i][j]-maze[i][j+1]);
                //上表面积的计算
                if(maze[i][j]) ans++;   
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-09-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏苦逼的码农

动态规划进阶篇1---背包问题

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装 入背包中物品的总价值最大?

1.6K3
来自专栏Java面试通关手册

六道面试中常见的智力题 来看看你会做几道?

下面的题目来自滴滴出行2017秋招题。这些题目是我自己觉得比较难或者比较容易出错的题目。

2294
来自专栏天天P图攻城狮

Android上实现频域均衡器

本篇文章主要介绍了将录音从时域数据转化成频域数据的方法。

4432
来自专栏友弟技术工作室

R语言入门

最近在复习python的科学计算,突然心血来潮,想看看R的数据处理和python的区别在哪,所以就有了这篇文章。 R语言简介 四十多年前, R 语言的始祖诞生了...

78111
来自专栏章鱼的慢慢技术路

OpenGL光照设置

1943
来自专栏大数据文摘

手把手 | 用StackOverflow访问数据实现主成分分析(PCA)

1517
来自专栏技术总结

iOS进阶之CAEmitterLayer

2948
来自专栏程序员的诗和远方

Canvas基础-粒子动画Part2

紧接上一篇文章 Canvas基础-粒子动画Part1 其实这篇早在一个星期之前就应该发了,无奈事情太多,而且我又跑去写微信公众号了。 粒子动起来 有了上一...

3197
来自专栏WOLFRAM

偶述 Wolfram 中文分词算法

从 2000 年开始学习和使用 Mathematica,《Mathematica 演示项目笔记》作者,发表Wolfram Demonstrations Proj...

1552
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

O(1)效率的表面模糊算法优化。

     很久没有写文章了,主要是最近一段时间没有以前那么多空暇空间,内存和CPU占用率一致都很高,应前几日群里网友的要求,今天发个表面模糊的小程序来找回之前...

2466

扫码关注云+社区

领取腾讯云代金券