Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define Gene template< class
- #define Rics printer& operator,
- Gene c> struct rge{c b, e;};
- Gene c> rge<c> range(c i, c j){ return {i, j};}
- struct printer{
- ~printer(){cerr<<endl;}
- Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
- Rics(string x){cerr<<x;return *this;}
- Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
- Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
- Gene c >Rics(rge<c> x){
- *this,"["; for(auto it = x.b; it != x.e; ++it)
- *this,(it==x.b?"":", "),*it; return *this,"]";}
- };
- #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
- #define dbg(x) "[",#x,": ",(x),"] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int my_rand(int l, int r) {
- return uniform_int_distribution<int>(l, r) (rng);
- }
- int main() {
- // freopen("in.txt", "r", stdin);
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n, m, k;
- cin >> n >> m >> k;
- vector<string> grid(n);
- for(int i = 0; i < n; i++) cin >> grid[i];
- priority_queue<tuple<int,int,int>> pq;
- vector<vector<int>> dis(n, vector<int>(m, -1));
- for(int i = 0; i < k; i++) {
- int x, y, c;
- cin >> x >> y >> c;
- x--, y--;
- assert(grid[x][y] == '.');
- pq.push(make_tuple(c, x, y));
- dis[x][y] = c;
- }
- vector<int> dx = {0,0,+1,-1};
- vector<int> dy = {+1,-1,0,0};
- int ans = 0;
- while(pq.size() > 0) {
- auto t = pq.top();
- int x = get<1>(t), y = get<2>(t);
- int c = get<0>(t);
- pq.pop();
- if(c == 0) continue;
- for(int k = 0; k < 4; k++) {
- int nx = x+dx[k], ny = y+dy[k];
- if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.' && dis[nx][ny] < c-1) {
- dis[nx][ny] = c-1;
- pq.push(make_tuple(c-1,nx,ny));
- }
- }
- }
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- ans += dis[i][j] != -1;
- }
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement