Massimizzare il numero di quadrati selezionati in una griglia

Question

Abbiamo una griglia di quadrati $ n tempi n $, ogni piazza ha un numero intero non negativo. Due quadrati distinti sono vicini se condividono una riga o una colonna. Una selezione di quadrati è buona se ogni quadrato selezionato ha un numero di vicini selezionati inferiori o uguali al suo numero.

C'è un modo noto per trovare il numero massimo di elementi in una buona selezione? Chiaramente c'è un $ mathcal o (2^{n^2} n^2) $ algoritmo di forza bruta (possiamo testare la bontà di una selezione in tempo $ mathcal o (n^2) $ quadrati in ogni riga e colonna).