Keskustelu: Ohjelmointikysymykset: Java: Matriisin suurimman yhtenäisen alueen etsiminen

Pitäisi tehdä eräs haastavampi ohjelmointitehtävä kouluun. Tehtvänanto kuuluu näin:

Kirjoita metodi laskeSuurinAlue(int[][] matriisi), jolle annetaan matriisi, jossa on vain ykkösiä ja nollia. Tehtävänäsi on laskea annetun matriisin suurin yhtenäinen alue, joka koostuu ykkösistä. Aluetta etsiessä liikkua saa vain ylös, alas, oikealle ja vasemmalle.

Esimerkiksi metodikutsu laskeSuurinAlue matriisille

0 1 0 0
1 1 1 0
0 0 0 1

palauttaa 4.

Olen aloittanut ohjelmoinnin, mutta en oikein ole edennyt. Tällä hetkellä koodini näyttää tältä:

public static int laskeSuurinAlue(int[][] matriisi){
    int Koko = 0;
    for(int i = 0; i < matriisi.length; i++){
        for(int j = 0; j < matriisi[i].length; j++){
            if(matriisi[i][j] == 1){
                Koko += viereisia(matriisi, i, j);
            }
        }
    }
    return Koko;
}

public static int viereisia(int i, int j, int[][] matriisi){
    int ViereistenMaara = 0;

    if(i > 0 && matriisi[i-1][j] == 1){
        matriisi[i-1][j] = 0;
        ViereistenMaara += viereisia(matriisi, i-1, j);
        ViereistenMaara ++;
    }


    if(j > 0 && matriisi[i][j-1] == 1){
        matriisi[i][j-1] = 0;
        ViereistenMaara += viereisia(matriisi, i, j);
        ViereistenMaara ++;
    }

    if(i < matriisi.length - 1 && matriisi[i+1][j] == 1){
        matriisi[i+1][j] = 0;
        ViereistenMaara += viereisia(matriisi, i+1, j);
        ViereistenMaara ++;
    }



    if(j < matriisi.length - 1 && matriisi[i][j+1] == 1){
        matriisi[i][j+1] = 0;
        ViereistenMaara += viereisia(matriisi, i, j+1);
        ViereistenMaara ++;
    }




    return ViereistenMaara ;
}

Vihjeet ja johdattelu ratkaisuun ovat tervetulleita.

PS. koodin ulkoasu voi olla huno, olen vasta alkanut koodaamaan.

Helpoin tapa varmaan olisi silmukassa tutkia ruudut missä ei ole käyty rekursiivisesti vähän samaan tapaan kuin miinaharavan zero cascade toteutus toimisi. Eli merkitset läpikäydessä samalla ruudun tilan käydyksi, jotta suoritus pysähtyy kun kaikki ruudut on läpikäyty. Kannattaa myös matriisin alueen ympärille lisätä ylimääräiset ruudut ja merkitä niiden tila läpikäydyksi, jotta ei tarvitse erikseen tarkastaa ollaanko matriisin alueen reunalla.

Toteutuksen voi tehdä myös kokonaan iteratiivisesti käyttämällä apuna jonoa...

Koodi ei käänny, koska olet sekoittanut funktion parametrien järjestyksen.

Koodin logiikan virhe on se, että lasket yhteen kaikki alueet (koko += viereisiä), vaikka tavoitteena on hakea vain suurin alue (koko = max(koko, viereisiä)).

Hakufunktion logiikka näyttää sinänsä oikealta. Kuitenkin tuossa et laske erikseen ensimmäistä ruutua, joten koodisi ei löydä yhden ruudun kokoisia alueita lainkaan. Isommat alueet se laskee oikein, koska haku palaa viereisestä ruudusta myös ensimmäiseen ruutuun.

Hakufunktio olisi lyhyempi ja selvempi, jos siinä ei käsiteltäisi samanlaisella koodilla jokaista neljää viereistä kohtaa vaan käsiteltäisiin nimenomaan parametrina annettu kohta. Eli funktio olisi tällainen:

if (0 <= i && i < matriisi.length && 0 <= j && j < matriisi[i].length) {
  if (matriisi[i][j] == 1) {
    matriisi[i][j] = 0;
    return 1
      + viereisiä(i + 1, j, matriisi)
      + viereisiä(i - 1, j, matriisi)
      + viereisiä(i, j + 1, matriisi)
      + viereisiä(i, j - 1, matriisi);
  }
}
return 0;

Metabolix kiitos! Juuri tuota koko = max(koko, viereisiä) juttua hain. Parametrien järjestyksen sekoitus johtui siitä, kun siirsin koodia tänne, enkä pystynyt suoraan copy pastemaan.