Selecție CPPI 2024 - Mirror Seniori | Enclava

Cerință

Harta unei insule este codificată sub forma unei matrice cu $n$ linii și $m$ coloane cu valori numere naturale. Cele $n \times m$ celule sunt de uscat și în jurul matricei este marea. Orice celulă este identificată printr-o pereche $(i,j)$ care indică linia și coloana pe care o ocupă. Liniile sunt numerotate de la $1$ la $n$ și coloanele de la $1$ la $m$. Două celule se consideră vecine dacă se află una lângă alta pe aceeași linie sau pe aceeași coloană.

Numim țară un grup maximal de celule care au aceeași valoare și între care se poate face deplasarea trecând dintr-o celulă în alta vecină o dată sau de mai multe ori.

O “enclavă” este o țară care are un singur vecin. Dacă țara este vecină și cu marea nu se mai consideră enclavă. O țară care conține o enclavă se numește “țară înfășurătoare”.

Dacă două sau mai multe țări, prin unire, ajung să formeze o enclavă, țara care le înconjoară este de asemenea considerată țară înfășurătoare (prin unire ne imaginăm că toate celulele țărilor care se unesc primesc aceeași valoare, a uneia oarecare dintre ele).

Problema cere să răspundem la interogări care precizează o țară (prin una dintre celulelel sale) și cer să spunem dacă ea este sau nu înfășurătoare.

Date de intrare

Fișierul enclava.in conține pe prima linie două numere naturale $n$ și $m$ cu semnificația de mai sus.
Pe următoarele $n$ linii sunt câte $m$ numere, separate prin spațiu, descriind insula.
Pe linia următoare se află o valoare $k$ care reprezintă numărul de interogări.
Pe fiecare din următoarele linii se află câte două valori reprezentând respectiv, linia și coloana unei celule.

Date de ieșire

Fișierul enclava.out conține pe prima linie, $k$ valori de $0$ și $1$, neseparate prin spațiu, reprezentând rezultatul interogării pentru țara care conține celula corespunzătoare dată în fișierul de intrare.

Restricții și precizări

• $3 \leq n \leq 100$;
• $3 \leq m \leq 100$;
• $1 \leq k \leq 1 \ 000$;
• Valorile din matrice sunt numere naturale de o cifră.

Exemplu

enclava.in

6 7
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 2 3 3 1 1
0 1 2 2 1 1 0
0 1 1 1 1 4 4
0 0 0 0 0 4 3
6
2 3
3 3
3 4
5 3
6 6
6 7

enclava.out

100100

Explicație

Avem două țări codificate cu valoarea $0$, o țară codificată cu valoarea $1$, una codificată cu valoarea $2$, una codificată cu valoarea $4$ și două codificate cu valoarea $3$.

Țara codificată cu $1$ este o țară înfășurătoare (țările codificate cu $2$ și $3$ (cea de mai sus) prin unire formează o enclavă înconjurată de ea). Țara codificată cu $4$, cea codificată cu $3$ în dreapta jos și cele codificate cu $0$ nu sunt înfășurătoare.