Tävlingsprogrammering/Uppgifter/Begränsningsarea

Begränsningsarea - Uppgift 3 - Onlinekvalet till PO 2007

Betrakta den tredimensionalla figuren ovan. Den är ihopsatt av ett antal 1x1x1 kuber i ett 3d-rutnät. Om vi begränsar oss till figurer som har staplar fästa i "marken", kan figuren på bilden beskrivas genom att ange höjden för varje stapel:

4 2 3 1

2 1 0 1

0 0 0 1

Figurens volym är förstås enkel att beräkna, men här är vi intresserade av dess begränsningsarea, d.v.s. antalet 1x1 kvadrater som är synliga utifrån (inklusive underifrån). Skriv ett program som beräknar detta, givet beskrivningen av en figur.

Indata

På första raden står två heltal r och k, där 1 ≤ r,k ≤ 50. Sedan följer r rader med k heltal på varje rad: höjden (≤ 50) för varje stapel.

Utdata

Programmet ska skriva ut ett heltal: figurens begränsningsarea.

Exempel: Indata

3 4

4 2 3 1

2 1 0 1

0 0 0 1

Exempel: Utdata

54

Lösning

Man kan helt enkelt loopa igenom alla max 50x50x50 kuber och undersöka vilka av dess sex sidor som är synliga genom att undersöka om det finns en granne mot den sidan.

Exempellösningen fungerar så här:

1. Läs in antalet rader och kolumner
2. Läs in höjden i varje stapel
3. Loopa igenom alla kuber och räkna antalet synliga sidor
4. Skriv ut sammanlagda antalet synliga sidor

Exempellösning i C++:

//Onlinekvalet till PO 2007
//Uppgift 3 - Begränsningsarea

#include <iostream>
using namespace std;

int main(void){
  int x, y, z, w, h;
  int nArea;                                              //begränsningsarean
  int cube[50][50];                                       //själva klossen
 
    //----------------------- läs in datan -------------------------------
    cin >> h >> w;                                        //läs in antalet rader och kolumner
    for(y = 0; y <= h - 1; y++){                          //loopa igenom y-kordinaterna
      for(x = 0; x <= w - 1; x++){                        //loopa igenom x-kordinaterna
        cin >> cube[x][y];                                //spara höjden på stapel (x, y)
      }
    }
    //--------------------------------------------------------------------------------

    nArea = 0;                                            //startvärde på arean är noll
    for(y = 0; y <= h - 1; y++){                          //loopa igenom y-kordinaterna
      for(x = 0; x <= w - 1; x++){                        //loopa igenom x-kordinaterna
        for(z = 1; z <= cube[x][y]; z++){                 //loopa igenom z-kordinaterna
          //kolla topp-/bottensidan:
          if(z == cube[x][y]) nArea++;                    //ingen kub ovanför;   synlig sida
          if(z == 1)          nArea++;                    //ingen kub under;     synlig sida
          
          //kolla vänster-/högersidan:
          if(x == 0     || cube[x - 1][y] < z) nArea++;   //stapeln till vänster är lägre; synlig sida
          if(x == w - 1 || cube[x + 1][y] < z) nArea++;   //stapeln till höger är lägre;   synlig sida

          //kolla bak/framsidan:
          if(y == 0     || cube[x][y - 1] < z) nArea++;   //stapeln bakom är lägre;       synlig sida
          if(y == h - 1 || cube[x][y + 1] < z) nArea++;   //stapeln framför är lägre;      synlig sida
        }
      }
    }
  }

  cout << nArea << "\n";                                  //printa begränsningsarean
  return 0;
}

En annan lösning är att beräkna begränsningsarean för de enskilda staplarna, och sedan ta bort de sidor som är gemensamma mellan två staplar. Metoden är enklare och går troligtvis snabbare, även om det bara fungerar på staplar.

#include <vector>
#include <algorithm>
#include <iostream>

int main(){
	size_t h,w;
	std::cin >> h >> w;
	std::vector<std::vector<size_t> > fig(h);
	size_t area=0;
	//Input och preliminär beräkning av arean
	for(size_t i=0;i<h;++i){
		fig[i].resize(w);
		for(size_t j=0;j<w;++j){
			std::cin >> fig[i][j];
			if(fig[i][j])area+=fig[i][j]*4+2;
		}
	}
	//Efterberäkning
	for(size_t i=0;i<h;++i)
		for(size_t j=0;j<w-1;++j)
			area-=2*std::min(fig[i][j],fig[i][j+1]);
	for(size_t i=0;i<h-1;++i)
		for(size_t j=0;j<w;++j)
			area-=2*std::min(fig[i][j],fig[i+1][j]);
	std::cout << area << std::endl;
	return 0;
}