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
redigeraMan 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:
- Läs in antalet rader och kolumner
- Läs in höjden i varje stapel
- Loopa igenom alla kuber och räkna antalet synliga sidor
- 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; }