Advertisement
_ash__

Untitled

Dec 10th, 2020
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Gene template< class
  5. #define Rics printer& operator,
  6. Gene c> struct rge{c b, e;};
  7. Gene c> rge<c> range(c i, c j){ return {i, j};}
  8. struct printer{
  9. ~printer(){cerr<<endl;}
  10. Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
  11. Rics(string x){cerr<<x;return *this;}
  12. Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
  13. Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
  14. Gene c >Rics(rge<c> x){
  15. *this,"["; for(auto it = x.b; it != x.e; ++it)
  16. *this,(it==x.b?"":", "),*it; return *this,"]";}
  17. };
  18. #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
  19. #define dbg(x) "[",#x,": ",(x),"] "
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21. int my_rand(int l, int r) {
  22. return uniform_int_distribution<int>(l, r) (rng);
  23. }
  24.  
  25.  
  26. int main() {
  27. // freopen("in.txt", "r", stdin);
  28. ios::sync_with_stdio(0);
  29. cin.tie(0);
  30.  
  31. int n, m, k;
  32. cin >> n >> m >> k;
  33. vector<string> grid(n);
  34. for(int i = 0; i < n; i++) cin >> grid[i];
  35. priority_queue<tuple<int,int,int>> pq;
  36. vector<vector<int>> dis(n, vector<int>(m, -1));
  37. for(int i = 0; i < k; i++) {
  38. int x, y, c;
  39. cin >> x >> y >> c;
  40. x--, y--;
  41. assert(grid[x][y] == '.');
  42. pq.push(make_tuple(c, x, y));
  43. dis[x][y] = c;
  44. }
  45. vector<int> dx = {0,0,+1,-1};
  46. vector<int> dy = {+1,-1,0,0};
  47. int ans = 0;
  48. while(pq.size() > 0) {
  49. auto t = pq.top();
  50. int x = get<1>(t), y = get<2>(t);
  51. int c = get<0>(t);
  52. pq.pop();
  53. if(c == 0) continue;
  54. for(int k = 0; k < 4; k++) {
  55. int nx = x+dx[k], ny = y+dy[k];
  56. if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.' && dis[nx][ny] < c-1) {
  57. dis[nx][ny] = c-1;
  58. pq.push(make_tuple(c-1,nx,ny));
  59. }
  60. }
  61. }
  62. for(int i = 0; i < n; i++) {
  63. for(int j = 0; j < m; j++) {
  64. ans += dis[i][j] != -1;
  65. }
  66. }
  67. cout << ans << endl;
  68. }
  69.  
  70.  
  71.  
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement