House Building
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 145 Accepted Submission(s): 123
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.
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.
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).
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.
1≤T≤50
1≤n,m≤50
0≤ci,j≤1000
3 3
1 0 0
3 1 2
1 1 0
3 3
1 0 1
0 0 0
1 0 1
20
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define MLL (1000000000000000001LL)
#define INF (1000000001)
#define For(i, s, t) for(int i = (s); i <= (t); i ++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i --)
#define Rep(i, n) for(int i = (0); i < (n); i ++)
#define Repn(i, n) for(int i = (n)-1; i >= (0); i --)
#define mk make_pair
#define ft first
#define sd second
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define sz(x) ((int) (x).size())
inline void SetIO(string Name)
{
string Input = Name + ".in";
string Output = Name + ".out";
freopen(Input.c_str(), "r", stdin);
freopen(Output.c_str(), "w", stdout);
} inline int Getint()
{
char ch = ' ';
int Ret = ;
bool Flag = ;
while(!(ch >= '' && ch <= ''))
{
if(ch == '-') Flag ^= ;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
Ret = Ret * + ch - '';
ch = getchar();
}
return Ret;
} const int N = , Dx[] = {, , -, }, Dy[] = {, , , -};
int n, m, Map[N][N]; inline void Solve(); inline void Input()
{
int TestNumber = Getint();
while(TestNumber--)
{
n = Getint();
m = Getint();
For(i, , n)
For(j, , m) Map[i][j] = Getint();
Solve();
}
} inline void Solve()
{
int Ans = ;
For(i, , n + ) Map[i][m + ] = ;
For(i, , m + ) Map[n + ][i] = ;
For(i, , n)
For(j, , m) {
if(!Map[i][j]) continue;
Ans ++;
Rep(k, )
{
int x = i + Dx[k], y = j + Dy[k];
if(Map[x][y] >= Map[i][j]) continue;
Ans += Map[i][j] - Map[x][y];
}
}
printf("%d\n", Ans);
} int main()
{
Input();
//Solve();
return ;
}