Problem 11: Größtes Produkt in einem Gitter

Gesucht wird das größte Produkt von 4 neben einander stehenden Zahlen (in allen Richtungen) in einem 20×20 Gitter! [das englische Original]

Um diese Aufgabe zu lösen, habe ich mir eine Matrix-Klasse entwickelt. Objekte dieser Klasse können Matrizen beliebiger Dimensionen darstellen, auch wenn für dieses Problem ausschließlich quadratische Matrizen benötigt werden. Hier konnte ich die Berechnung des maximalen Produktes in einer Zeile, Spalte oder Diagonale auslagern. Außerdem war so der Export einer 4×4-Sub-Matrix auf dem gegebenen Gitter recht einfach:

public String solve() {

   long max = 0, tmp;

   for( int y = 0; y <= 16; y++ ) {
      for( int x = 0; x <= 16; x++ ) {
         Matrix cur = grid.getSection( x, y, 4 );
         tmp = cur.findMaxProduct( true );
         if( tmp > max ) {
            IO.debugln( "found new max " + tmp + " in section at " + x + ":" + y );
            max = tmp;
         }
      }
   }

   return IO.l2s( max );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 11 kann man sich hier anschauen!

<< Problem 10 Übersicht Problem 12 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: