Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- #define pii pair<int, int>
- #define f first
- #define s second
- /// U UR R DR D DL L UL
- pii ctrl[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
- vector<vector<bool>> light;
- int row, col;
- void AddLight(pii s){
- queue<pii> q; /// (row, col)
- light[s.f][s.s] = false;
- q.emplace(s.f, s.s);
- while(!q.empty()){
- int ur = q.front().f;
- int uc = q.front().s;
- q.pop();
- for(int i = 0; i < 8; ++i){
- int vr = ur + ctrl[i].f;
- int vc = uc + ctrl[i].s;
- if(vr <= row && vr > 0 && vc <= col && vc > 0){
- if(light[vr][vc]){
- light[vr][vc] = false;
- q.emplace(vr, vc);
- }
- }
- }
- }
- return;
- }
- int main(){
- char c;
- int cnt;
- scanf("%d %d", &row, &col);
- light.assign(row + 1, vector<bool>(col + 1, false));
- for(int i = 1; i <= row; ++i){
- for(int j = 1; j <= col; ++j){
- scanf(" %c", &c);
- if(c == '1'){
- light[i][j] = true;
- }
- }
- }
- cnt = 0;
- for(int i = 1; i <= row; ++i){
- for(int j = 1; j <= col; ++j){
- if(light[i][j]){
- ++cnt;
- AddLight({i, j});
- }
- }
- }
- cout << cnt;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement