SHARE
TWEET

847I

a guest Oct 12th, 2017 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int n, m, q, p;
  7. int bfs_tab[253][253];
  8. char t[253][253];
  9. int sum[253][253];
  10.  
  11. //pair <int, int> qq;
  12. queue < pair<int, int> > Q;
  13.  
  14. const int d_x[4] = {-1, 0, 1, 0};
  15. const int d_y[4] = {0, 1, 0, -1};
  16.  
  17.  
  18. int pow2 (int y)
  19. {
  20.     int w = 1;
  21.     for (int i = 0; i < y; i++)
  22.         w*=2;
  23.        
  24.         return w;
  25. }
  26.  
  27. void bfs(int a, int b);
  28.  
  29. int main (){
  30.  
  31. cin >> n >> m >> q >> p;
  32.  
  33. for (int i = 0; i < n; i++)
  34.     for (int j = 0; j < m; j++)
  35.        cin >> t[i][j];
  36.  
  37. for (int i = 0; i < n; i++)
  38.     for (int j = 0; j < m; j++)
  39.     {
  40.         if (t[i][j] >= 'A' && t[i][j] <= 'Z')
  41.         {
  42.             bfs(i, j);  
  43.            
  44.         /*  for (int i = 0; i < n; i++)
  45.             {
  46.                 for (int j = 0; j < m; j++)
  47.                         cout << bfs_tab[i][j] << " ";
  48.                         cout << endl;
  49.             }
  50.                 cout << endl;*/
  51.         }
  52.  
  53.     }
  54.  
  55.  
  56. int sol=0;
  57.  
  58.        
  59. for (int i = 0; i < n; i++)
  60.     for (int j = 0; j < m; j++)
  61.         if (sum[i][j]>p)
  62.             sol++;
  63.            
  64.            
  65.             cout << sol;
  66.  
  67.  
  68.  
  69. return 0;
  70.  
  71.  
  72.  
  73. }
  74.  
  75.  
  76. void bfs(int a, int b)
  77. {
  78.     while (!Q.empty())
  79.         Q.pop();
  80.        
  81.      for (int i2 = 0; i2 < n; i2++)
  82.         for (int j2 = 0; j2 < m; j2++)
  83.             bfs_tab[i2][j2]=0;
  84.            
  85.     //bool pot = false;
  86.     //qq=make_pair(a, b);
  87.     int value=q*(t[a][b]-64);
  88.     bfs_tab[a][b]=1;
  89.     sum[a][b]+=value;
  90.  
  91.     for (Q.push(make_pair(a, b)); !Q.empty(); Q.pop())
  92.     {
  93.         pair <int, int> qq = Q.front();
  94.              
  95.         if (value/pow2(bfs_tab[qq.first][qq.second])==0)
  96.             break;  
  97.        
  98.         for (int k = 0; k < 4; k++)
  99.         {
  100.             int a1=qq.first+d_x[k];
  101.             int b1=qq.second+d_y[k];
  102.  
  103.             if (a1 < n && a1 >= 0 && b1 < m && b1 >= 0 && bfs_tab[a1][b1]==0 && t[a1][b1]!='*')
  104.             {
  105.                 bfs_tab[a1][b1]=bfs_tab[qq.first][qq.second]+1;
  106.                 sum[a1][b1]+=value/pow2(bfs_tab[qq.first][qq.second]);
  107.            
  108.                 Q.push(make_pair(a1, b1));
  109.             }
  110.         }
  111.        
  112.     }
  113.  
  114. }
RAW Paste Data
Top