Question

#884 pbinfo
Cerința
Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.

Date de intrare
Fișierul de intrare paznici.in conține pe prima linie trei numere n m p, reprezentând dimensiunile clădirii şi numărul de paznici.

Urmează n linii cu câte m caractere, care pot fi: -, reprezentând o cameră liberă, respectiv #, reprezentând o cameră ocupată.

Urmează p linii cu câte 3 valori i j d, reprezentând informaţiile despre paznici. i j reprezintă indicii camerei, iar d reprezintă distanţa pe care se poate deplasa acel paznic.

Date de ieșire
Fișierul de ieșire paznici.out va conține pe prima linie numărul C de camere care nu sunt vizitate de niciun paznic.

Restricții și precizări
1 ≤ n , m , p ≤ 200
1 ≤ i ≤ n
1 ≤ j ≤ m
0 ≤ d ≤ 40

Answer 1

#include <fstream>

using namespace std;

char harta[202][202];

struct paznic{int x, y, d;};

struct ec{int x, y;};

ec elemente[15000];

void adaugavecini(int& k, ec x){

if(harta[x.x+1][x.y] == '-' || harta[x.x+1][x.y] == 'e'){

harta[x.x+1][x.y]='c';

elemente[k].x = x.x+1;

elemente[k].y= x.y;

k++;

}

if(harta[x.x-1][x.y] == '-' || harta[x.x-1][x.y] == 'e'){

harta[x.x-1][x.y]='c';

elemente[k].x = x.x-1;

elemente[k].y= x.y;

k++;

}

if(harta[x.x][x.y+1] == '-' || harta[x.x][x.y+1] == 'e'){

harta[x.x][x.y+1]='c';

elemente[k].x = x.x;

elemente[k].y= x.y+1;

k++;

}

if(harta[x.x][x.y-1] == '-' || harta[x.x][x.y-1] == 'e'){

harta[x.x][x.y-1]='c';

elemente[k].x = x.x;

elemente[k].y= x.y-1;

k++;

}

}

void proc(paznic p){

int d = 0;

if(harta[p.x][p.y]=='#')return;

harta[p.x][p.y] = 'c';

elemente[0].x = p.x;

elemente[0].y = p.y;

int k = 1;

int lk = 0;

while(d < p.d){

int kc = k;

for(int i = lk; i < kc; i++)

adaugavecini(k, elemente[i]);

if(k==kc)break;

lk = kc;

d++;

}

for(int i = 0; i < k; i++){

ec x = elemente[i];

harta[x.x][x.y]='e';

}

}

int main(){

int n,m, p;

ifstream fin("paznici.in");

ofstream fout("paznici.out");

fin >> n >> m >> p;

for(int i = 1; i <= n; i++){

for(int j = 1; j <= m; j++){

fin >> harta[i][j];

}

}

for(int i = 0; i <= n+1; i++){

harta[i][0] = harta[i][m+1] = '#';

}

for(int i = 0; i <= m+1; i++){

harta[0][i] = harta[n+1][i] = '#';

}

for(int i = 0; i < p; i++){

paznic paz;

fin >> paz.x>>paz.y >> paz.d;

proc(paz);

}

fin.close();

int r = 0;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++){

if(harta[i][j] == '-')r++;

}

fout << r;

fout.close();

}