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 ≤ 2001 ≤ i ≤ n1 ≤ j ≤ m0 ≤ d ≤ 40
Exemplu
paznici.in
4 6 3 --#-#- --##-- ------ -----# 1 1 1 1 6 2 4 1 3
paznici.out
4
Explicație
Mai jos sunt marcate cu 1 2 3 camerele în care ajung paznicii respectivi. În unele camere pot să ajungă mai mulţi paznici.
| 1 | 1 | – | 2 | ||
| 1 | 3 | 2 | 2 | ||
| 3 | 3 | 3 | – | – | 2 |
| 3 | 3 | 3 | 3 | – | |
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Paznici:
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("paznici.in");
ofstream fout("paznici.out");
int n , m , p;
int a[201][201];
short x[40005], y[40001];
char P[201][201];
const int dx[] = {0 , 0 , 1 , -1},
dy[] = {1 , -1 , 0 , 0};
void fill (int i ,int j , int d)
{
int st , dr;
st = dr = 1;
x[1] = i , y[1] = j;
a[i][j] = 1;
P[i][j] = '*';
while(st <= dr)
{
int i = x[st], j = y[st];
if(a[i][j] <= d)
for(int k = 0 ; k < 4 ; k ++)
{
int ii = i + dx[k], jj = j + dy[k];
if( ii > 0 && ii <= n && jj > 0 && jj <= m && P[ii][jj] !='#' && a[ii][jj] == 0)
{
a[ii][jj] = a[i][j] + 1;
P[ii][jj] = '*';
dr ++;
x[dr] = ii, y[dr] = jj;
}
}
st ++;
}
}
void resetare()
{
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
a[i][j] = 0;
}
int main(){
fin >> n >> m >> p;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
fin >> P[i][j];
for ( ; p ; p --)
{
resetare();
int i , j , d;
fin >> i >> j >> d;
if(a[i][j] == 0)
fill(i,j,d);
}
int cnt = 0;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
if(P[i][j] == '-' && a[i][j] == 0)
cnt ++;
fout << cnt;
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #884 Paznici
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #884 Paznici de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!