Advertisement
mickypinata

TOI11: Candle Lighting Prayer

Apr 22nd, 2020
740
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. #define pii pair<int, int>
  7. #define f first
  8. #define s second
  9.  
  10. /// U UR R DR D DL L UL
  11. pii ctrl[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
  12. vector<vector<bool>> light;
  13. int row, col;
  14.  
  15. void AddLight(pii s){
  16.     queue<pii> q; /// (row, col)
  17.     light[s.f][s.s] = false;
  18.     q.emplace(s.f, s.s);
  19.     while(!q.empty()){
  20.         int ur = q.front().f;
  21.         int uc = q.front().s;
  22.         q.pop();
  23.         for(int i = 0; i < 8; ++i){
  24.             int vr = ur + ctrl[i].f;
  25.             int vc = uc + ctrl[i].s;
  26.             if(vr <= row && vr > 0 && vc <= col && vc > 0){
  27.                 if(light[vr][vc]){
  28.                     light[vr][vc] = false;
  29.                     q.emplace(vr, vc);
  30.                 }
  31.             }
  32.         }
  33.     }
  34.     return;
  35. }
  36.  
  37. int main(){
  38.  
  39.     char c;
  40.     int cnt;
  41.  
  42.     scanf("%d %d", &row, &col);
  43.     light.assign(row + 1, vector<bool>(col + 1, false));
  44.     for(int i = 1; i <= row; ++i){
  45.         for(int j = 1; j <= col; ++j){
  46.             scanf(" %c", &c);
  47.             if(c == '1'){
  48.                 light[i][j] = true;
  49.             }
  50.         }
  51.     }
  52.  
  53.     cnt = 0;
  54.     for(int i = 1; i <= row; ++i){
  55.         for(int j = 1; j <= col; ++j){
  56.             if(light[i][j]){
  57.                 ++cnt;
  58.                 AddLight({i, j});
  59.             }
  60.         }
  61.     }
  62.  
  63.     cout << cnt;
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement