Campo da calcio

Aiuto
1

ho fatto questo codice per il problema campo da calcio, fa bene i due casi test di esempio ma poi fa solo uno o due casi di test (alle volte 0).
Qualcuno sa aiutarmi?

#include <iostream>
#include <vector>

using namespace std;
constexpr int NMAX = 7002;
int foresta[NMAX][NMAX];
int prefix[NMAX][NMAX];

void solve(int t) {
    int N, M, K, A, B;
    cin >> N >> M >> K >> A >> B;

    int x,y;
    for (int i = 0; i < K; i++) {
        cin >> x >> y;
        foresta[x][y]++;
    }

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            prefix[i][j] = prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+foresta[i-1][j-1];
        }
    }
    
    int risposta = 1e9;
    int tmp;
    for (int i=0; i<=N; i++) {
        for (int j=0; j<=M; j++) {
            if (i+A <= N && j+B <= M) {
                tmp = prefix[i+A][j+B] - prefix[i][B] - prefix[A][j] + prefix[i][j];
                if (tmp < risposta) risposta = tmp;
            }
        }
    }
    
    cout << "Case #" << t << ": " << risposta << "\n";
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}
2

Se non erro, il problema nel tuo codice si trova qui. Le somme prefisse non si calcolano sempre allo stesso modo per ogni posizione nella matrice, c’è una risposta diversa per:

  • if (i==0 && j==0), (se entrambi sono uguali a 0)
  • if (i==0), (se solo i è uguale a 0)
  • if (j==0), (se solo j è uguale a 0)
  • else, (se nessuno dei 2 è uguale a 0)

Tuttavia, la funzione che hai scritto non funziona in nessuno di questi casi (il fatto che i 2 test ti portino è un caso). Prova a ragionarci un po’, se avrai ancora bisogno di aiuto ti darò la soluzione.

Suggerimento: invece di mettere un if dentro ai 2 for, è meglio mettere le condizioni direttamente nei for, in questo modo

for (int i=0; i<N-A; i++) {
     for (int j=0; j<M-B; j++) {
         //soluzione che devi trovare
     }
}

Non cambia niente a livello di funzionalità, ma aumenta la leggibilità e riduce il rischio di fare errori