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

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.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("paznici.in");
ofstream cout("paznici.out");

const int di[] = {0 , 0 , -1 , 1};
const int dj[] = {-1 , 1 , 0 , 0};

struct poz
{
    int i , j;
};

int n , m , t , x , y , val , cnt , a[201][201] , b[201][201] , c[201][201];
char ma[202][202];

queue <poz>q;

int inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m ;
}

void lee(int x , int y , int val)
{
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            a[i][j] = b[i][j];
    a[x][y] = 1;

    poz r;
    r.i = x , r.j = y;
    q.push(r);
    while(!q.empty())
    {
        poz nou;
        nou = q.front();
        for(int d = 0 ; d < 4 ; d++)
        {
            int inou = nou.i + di[d];
            int jnou = nou.j + dj[d];
            if(inside(inou , jnou) && a[inou][jnou] == 0 && a[nou.i][nou.j] <= val)
            {
                a[inou][jnou] = a[nou.i][nou.j] + 1;
                q.push({inou , jnou});
            }
        }
        q.pop();
    }
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            if(c[i][j] == 0) c[i][j] = a[i][j];

}

int main()
{
    cin >> n >> m >> t;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> ma[i][j];
            if(ma[i][j] == '#') a[i][j] = -1 , b[i][j] = -1;
        }
    for(int i = 1 ; i <= t ; i++)
    {
        cin >> x >> y >> val;
        lee(x , y , val);

    }
    /*for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= m ; j++)
            cout << c[i][j] << " ";
        cout << '\n';
    }*/
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j++)
            if(c[i][j] == 0) cnt++;
    cout << cnt;
}