Enclava

Time limit: 0.4s Memory limit: 64MB Input: enclava.in Output: enclava.out

Cerință

Harta unei insule este codificată sub forma unei matrice cu nn linii și mm coloane cu valori numere naturale. Cele n×mn \times m celule sunt de uscat și în jurul matricei este marea. Orice celulă este identificată printr-o pereche (i,j)(i,j) care indică linia și coloana pe care o ocupă. Liniile sunt numerotate de la 11 la nn și coloanele de la 11 la mm. 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 nn și mm cu semnificația de mai sus.
Pe următoarele nn linii sunt câte mm numere, separate prin spațiu, descriind insula.
Pe linia următoare se află o valoare kk 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, kk valori de 00 și 11, 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

  • 3n1003 \leq n \leq 100;
  • 3m1003 \leq m \leq 100;
  • 1k1 0001 \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 00, o țară codificată cu valoarea 11, una codificată cu valoarea 22, una codificată cu valoarea 44 și două codificate cu valoarea 33.

Țara codificată cu 11 este o țară înfășurătoare (țările codificate cu 22 și 33 (cea de mai sus) prin unire formează o enclavă înconjurată de ea). Țara codificată cu 44, cea codificată cu 33 în dreapta jos și cele codificate cu 00 nu sunt înfășurătoare.

Log in or sign up to be able to send submissions!