numero di matrici quadrate in una matrice non quadrata [chiuso]

Bene, a prima vista sembra che tu voglia la soluzione "avida" che trova i quadrati più grandi possibili (piuttosto che usare tutti gli 1x1), quindi sembra semplicemente trovare il quadrato più grande possibile nella matrice corrente e poi ricorsivamente nella parte restante della matrice dovrebbe funzionare:

int squaresInRectangle(int m, int n) {
   if(m <= 0 || n <= 0) { return 0; }
   int largestPossibleSquareSize = min(m, n);
   int remainingSquareCount;
   if(m < n) {
       remainingSquareCount = squaresInRectangle(m, n - largestPossibleSquareSize);
   } else {
       remainingSquareCount = squaresInRectangle(m - largestPossibleSquareSize, n);
   }
   return 1 + remainingSquareCount;
}

Molti problemi possono essere risolti con un algoritmo greedy ricorsivo

Dato una matrice MxN , puoi sempre trovare una matrice KxK nell'angolo in alto a sinistra, dove K = Min(M,N) . Se si rimuove la parte dalla matrice, si ottiene un resto. Ripeti il processo su quella matrice fino a quando non finisci gli elementi.

Un esempio di esecuzione dell'algoritmo naive:

|0 0 0 1 1| => |0 0 0| % |1 1|
|0 0 0 1 1|    |0 0 0|   |1 1|
|0 0 0 2 3|    |0 0 0|   |2 3|

C'è ancora un resto della matrice.

|1 1| => |1 1| %  |2 3|
|1 1|    |1 1|
|2 3|

C'è ancora un resto della matrice.

|2 3| => |2| % |3|

C'è ancora un resto della matrice.

|3| => |3| % ||

Sembra che abbiamo finito, avendo finito le matrici. Uno 3x3 , uno 2x2 , due 1x1 .

E ricorda, se elimini le soluzioni per i compiti da qualche parte senza comprenderli e senza essere in grado di motivare ciò che hai detto nel tuo rapporto, la persona che stai imbrogliando di più è te stesso.

Molto simile all'algoritmo euclideo

int squaresInRectangle(int m, int n) {
    if (n <= 0) { return 0; }
    return squaresInRectangle(n, m % n) + (m / n);
}