Mali Đokica je dobio kockice za rođendan. Uzeo je tablu dimenzija n puta m i na svako polje je postavio nekoliko kockica (jednu na drugu). Time je napravio figuru koja ne mora da bude povezana. Njegov tata posmatra kako se mali Đokica igra i želi da zna zapreminu i površinu dobijenog tela.

Ulaz:

U prvom redu ulazne datoteke ZAD3.DAT nalaze se dva prirodna broja razdvojena prazninom n i m (1 ≤ n, m ≤ 500) i predstavljaju dimenzije table. U svakom od sledećih n redova se nalazi m brojeva. U i-tom redu j-ti broj a[i][j] (0 ≤ a[i][j] ≤ 1000) označava visinu stuba (broj kockica) na tom polju.

Izlaz:

U izlaznu datoteku ZAD3.RES ispisati zapreminu i površinu tela koje je mali Đokica napravio.

Primer:

2 3
2 2 2
1 0 3

10 36

Objašnjenje:

Figura na slici odgovara rasporedu kockica u test primeru. Zapremina tela je 10, dok je površina 36.

Zapremina tela je jednaka broju kockica koje je Đokica upotrebio – suma svih brojeva u matrici a.

Površinu tela računamo kao zbir svih horizontalnih i vertikalnih vidljivih strana kockica. Broj horizontalnih strana je jednak dvostrukom broju stubića, tj. dvostruki broj nenula elemenata matrice a. Kako bi lakše izračunali broj vertikalnih strana, uokvirimo datu matricu nulama. Broj strana koje su vidljive između dva stubića kockica je jednak apsolutnoj vrednosti razlike visina. Sada prođemo kroz matricu a, i za svako polje pogledamo desno i gore, sabirajući brojeve |a [i, j] – a [i + 1, j]| + |a [i, j] – a [i, j + 1]|.

Složenost algoritma je O (nm).

Pseudokod:

   for i = 0 to n + 1 do begin
      a [i][0] = 0;
      a [i][m + 1] = 0;
   end;
   for j = 0 to m do begin 
      a [0][j] = 0;
      a [n + 1][j] = 0;
   end;
   Volume = 0;
   Area = 0;
   for i = 0 to n do
      for j = 0 to m do begin
         Volume = Volume + a [i][j];
         if (a [i][j] > 0) then
            Area = Area + 2;
         Area = Area + abs (a [i + 1][j] – a [i][j]) + abs (a [i][j + 1] – a [i][j]);
      end;

#include <stdio.h>
#include <math.h>
#define MaxN 502

long n, m, a [MaxN][MaxN], Volume, Area;

void Input ()
{
  FILE *in;
  long i, j;

  in = fopen ("zad3.dat", "r");
  fscanf (in, "%ld %ld", &n, &m);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      fscanf (in, "%ld", &a [i][j]);
  fclose (in);
}

void Output ()
{
  FILE *out;

  out = fopen ("zad3.res", "w");
  fprintf (out, "%ld %ld\n", Volume, Area);
  fclose (out);
}

void Solve ()
{
  long i, j;

  Volume = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      Volume = Volume + a [i][j];

  for (i = 0; i <= n; i++)
  {
    a [i][0] = 0;
    a [i][m + 1] = 0;
  }
  for (j = 0; j <= m; j++)
  {
    a [0][j] = 0;
    a [n + 1][j] = 0;
  }
  Area = 0;
  for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++)
    {
      if (a [i][j] > 0)
        Area = Area + 2;
      Area = Area + abs (a [i][j] - a [i + 1][j]) + abs (a [i][j] - a [i][j + 1]);
    }
}

int main ()
{
  Input ();
  Solve ();
  Output ();
  return 0;
}