Opgaver i denne lektion        næste -- Tastaturgenvej: 'n'  Gå til slide, hvor denne opgave er tilknyttet -- Tastaturgenvej: 'u'  

Opgave 11.4
Opgave 1 side 587 i PSPD(8ed) - blob_count


Dette er hints til opgave 1 side 587 i Problem Solving and Program Design in C, 8ed (svarende til opgave 1 side 583 i 7ed).

Der findes en video som giver et oplæg til problemløsningen. Jeg anbefaler at I ser denne video forud for løsningen af opgaven.

Jeg synes det er mere naturligt at kalde funktionen blob_count i stedet for bogens forslag, blob_check.

Bogens grid, vist nederst side 587 (8ed), kan laves på denne måde:

  int grid[5][5] = {
                     {1, 1, 0, 0, 0},
                     {0, 1, 1, 0, 0},
                     {0, 0, 1, 0, 1},
                     {1, 0, 0, 0, 1},
                     {0, 1, 0, 1, 1},
                    };

Med denne opskrivning er det mest naturligt at x 'er lodret' (betegner rækker) og at 'y er vandret' (betegner søjler). Dette syn er altså lidt anderledes end bogens.

Bemærk at grid[0][0] er 1 (øverste venstre hjørne), grid[0][4] er 0 (øverste højre hjørne), grid[4][0] er 0 (nederste venstre hjørne), og at grid[4][4] er 1 (nederste højre hjørne).

Overvej nøje, hvordan du vil håndtere felter som falder uden for griddet (f.eks grid[-1][5]). Hint: Lad blob_count på sådanne felter returnere 0.

Som en centalt punkt i opgaven skal du besøge alle 8 naboer til et punkt i tabellen. Det kan være træls at gøre dette manuelt, nabo for nabo. Overvej hvordan dette kan gøres med (to nestede) for-løkker.

Vær sikker på at funktionen blob_count bliver rekursiv. Altså at funktionen kaldes rekursivt på alle 8 naboer af en celle. Ideen er at tælle blob størrelsen af eksempelvis celle (x+1,y+1) efter nøjagtig samme opskrift som blev anvendt til at tælle blob størrelsen af celle (x,y).

Som beskrevet i bogen er det nødvendigt at markere at en celle er talt. Dette gøres lettest ved at ændre 1-tallet til 0 i cellen. Dette ødelægger griddet. Jeg foreslår derfor at det givne grid kopieres over i et andet grid før kaldet af blob_count. På denne måde er det en kopi, som ødelægges, ikke originalen. Skriv gerne en copy_grid funktion, som udfører dette.

I main bør du indlæse et (x,y) punkt og kalde blob_count(x, y). Gør gerne dette i en løkke, så du kan undersøge flere (x,y) punkter i samme kørsel af programmet.


Løsning