/* XOR (IOI 2002) Copyright (C) 2003 Stefano Maggiolo This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Questo problema ha rappresentato una piccola innovazione nella storia delle IOI: per quanto il punteggio, come già successo in precedenza, venga assegnato tanto più alto quanto più il valore della soluzione si avvicini a quello ottimo, il valore ottimo è il migliore tra quelli generati dalle soluzioni di tutti i partecipanti alla gara. Il motivo di questo cambiamento è da ricercarsi nella natura del problema: le soluzioni corrette, infatti, non termineranno in tempi umani. L'organizzazione, quindi, non aveva a disposizione i risultati ottimali. Il non poter risolvere perfettamente il problema porta a dover implementare un qualche tipo di soluzione approssimata. Una di queste (non la migliore) portata come esempio dai propositori del problema si distingue per la semplicità di comprensione e di implementazione e per le buone prestazioni; si tratta di una 2-ottima: garantisce cioè di risolvere il problema in al più 2N chiamate, se N è il numero minimo di chiamate. Inizialmente osserviamo che ricostruire l'immagine, equivale a, partendo dall'immagine stessa, farla tornare completamente bianca. Definiamo ora il concetto di punto (della griglia) e di angolo (dell'immagine): un punto è un intersezione tra le righe e le colonne che dividono i pixel, tangente a 4 pixel se è al centro dello schermo, a 2 se è sui lati, a 1 se è all'angolo dello schermo; un angolo è un punto che è tangente ad un numero dispari di pixel neri. Se si chiama XOR su un qualsiasi rettangolo, si puo` osservare che gli unici punti che cambiano "l'angolosità" sono quelli agli angoli del rettangolo XORato. Infatti, i punti interni al rettangolo non cambiano, perché vengono invertiti tutti i 4 pixel adiacenti; cio` vale anche per i punti sui lati del rettangolo, perché vengono invertiti 2 dei pixel adiacenti; solo i punti agli angoli del rettangolo variano, perché viene invertito un solo pixel adiacente. Man mano che si inseriscono rettangoli verranno quindi inseriti o eliminati degli angoli. Tuttavia, la loro disposizione conserverà una proprietà: per ogni riga e ogni colonna della griglia, il numero degli angoli è sempre pari (inserendo un rettangolo, in due righe e due colonne vengono invertiti due valori di angolosità). Ciò ci permette di scegliere un qualsiasi angolo dell'immagine (viene scelto quello più in alto e, a parità, a destra) e trovarne altri due, uno sulla stessa riga e uno sulla stessa colonna. Con questi possiamo costruire un rettangolo che eliminerà due o quattro angoli a seconda del valore di angolosità del quarto angolo del rettangolo. Una volta terminati gli angoli, vorrà dire che l'immagine è tornata bianca. Nel caso peggiore, eliminando due angoli alla volta si utilizzeranno 2N chiamate, nel caso ottimo, quattro angoli alla volta, si useranno N chiamate. */ #include #include #include #define MAXN 2000 /* dimensione massima dello schermo */ #define MAXR 40000 /* numero massimo di rettangoli */ typedef struct { int r1, r2, c1, c2; } RECT; RECT rect[MAXR]; int nr; /* matrice dei pixel dell'immagine */ char m[MAXN][MAXN]; /* matrice dei punti della griglia */ char g[MAXN + 1][MAXN + 1]; /* dimensione della matrice */ int N; /* calcola i valori di angolosità dei punti dell'immagine iniziale */ void aggiorna_griglia(void) { int r, c; for (r = 0; r <= N; r++) for (c = 0; c <= N; c++) { if (r == 0 && c == 0) g[0][0] = m[0][0]; else if (r == 0 && c == N) g[0][N] = m[0][N - 1]; else if (r == MAXN && c == 0) g[N][0] = m[N - 1][0]; else if (r == N && c == N) g[N][N] = m[N - 1][N - 1]; else if (r == 0) g[0][c] = (m[0][c - 1] != m[0][c]); else if (c == 0) g[r][0] = (m[r - 1][0] != m[r][0]); else if (r == N) g[N][c] = (m[N - 1][c - 1] != m[N - 1][c]); else if (c == N) g[r][N] = (m[r - 1][N - 1] != m[r][N - 1]); else g[r][c] = ((m[r - 1][c - 1] + m[r][c - 1] + m[r - 1][c] + m[r][c]) % 2); } } int main(void) { int r, c, pr = 0; /* lettura input */ scanf("%d", &N); for (r = 0; r < N; r++) for (c = 0; c < N; c++) scanf("%c", &m[r][c]); aggiorna_griglia(); /* il ciclo termina quando non ci sono più angoli (cioè quando l'immagine ritorna bianca) */ for (;;) { int r1, r2, c1, c2; /* limiti del rettangolo da inserire nell'output */ /* viene cercato il primo angolo partendo dalla riga a cui si era arrivati (pr) e procedendo verso sinistra e verso il basso, che determina r1 e c2 (è l'angolo in alto a destra) */ for (r = pr; r <= N; r++) for (c = N; c >= 0; c--) if (g[r][c]) goto found; break; found: pr = r1 = r; c2 = c - 1; /* viene cercato il primo angolo sulla stessa riga alla sua sinistra, che determina c1 */ for (c--; c >= 0; c--) if (g[r][c]) break; c1 = c; /* il primo angolo sulla stessa colonna verso il basso, che determina r2 */ for (r++; r <= N; r++) if (g[r][c2 + 1]) break; r2 = r - 1; /* vengono invertiti i 4 valori di angolosità che cambiano */ g[r1][c1] = !g[r1][c1]; g[r2 + 1][c1] = !g[r2 + 1][c1]; g[r1][c2 + 1] = !g[r1][c2 + 1]; g[r2 + 1][c2 + 1] = !g[r2 + 1][c2 + 1]; /* e il rettangolo viene inserito in un'array, dato che dobbiamo saper dire il loro numero prima di stamparli */ rect[nr].r1 = r1 + 1; rect[nr].r2 = r2 + 1; rect[nr].c1 = c1 + 1; rect[nr].c2 = c2 + 1; nr++; /* sforato il numero massimo di rettangoli, si esce */ if (nr >= MAXR) break; } /* stampa dell'output */ printf("%d\n", nr); for (r = 0; r < nr; r++) printf("%d %d %d %d\n", rect[r].c1, rect[r].c2, rect[r].r1, rect[r].r2); return 0; }