fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. constexpr array<int, 4> DY = { -1, 1,  0, 0 };
  6. constexpr array<int, 4> DX = {  0, 0, -1, 1 };
  7.  
  8. constexpr int M = 210;
  9. constexpr int N = 210;
  10. int m, n;
  11. array<bitset<N>, N> mat, seen;
  12. array<array<int, N>, M> neighborCnt;
  13.  
  14. bool isInBounds(int y, int x) {
  15.     return 0 <= y && y < m && 0 <= x && x < n;
  16. }
  17.  
  18. bool bfs(int srcY, int srcX) {
  19.     queue<pair<int, int>> q;
  20.  
  21.     q.push(make_pair(srcY, srcX));
  22.     seen[srcY][srcX] = true;
  23.  
  24.     bool hasEndpoint = false;
  25.     bool canExtend = false;
  26.  
  27.     while (!q.empty()) {
  28.         int y, x;
  29.         tie(y, x) = q.front();
  30.         q.pop();
  31.  
  32.         if (neighborCnt[y][x] <= 1) {
  33.             hasEndpoint = true;
  34.         }
  35.  
  36.         for (int i = 0; i < 4; ++i) {
  37.             int yy = y + DY[i];
  38.             int xx = x + DX[i];
  39.  
  40.             if (isInBounds(yy, xx)) {
  41.                 if (mat[yy][xx]) {
  42.                     if (!seen[yy][xx]) {
  43.                         seen[yy][xx] = true;
  44.                         q.push(make_pair(yy, xx));
  45.                     }
  46.                 } else if (neighborCnt[y][x] <= 1 && neighborCnt[yy][xx] == 1) {
  47.                     canExtend = true;
  48.                 }
  49.             }
  50.         }
  51.     }
  52.  
  53.     return hasEndpoint && !canExtend;
  54. }
  55.  
  56. int main() {
  57.     if (fopen("RAN.inp", "r")) {
  58.         freopen("RAN.inp", "r", stdin);
  59.         freopen("RAN.out", "w", stdout);
  60.     }
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(nullptr);
  63.  
  64.     cin >> m >> n;
  65.  
  66.     for (int y = 0; y < m; ++y) {
  67.         for (int x = 0; x < n; ++x) {
  68.             char tmp;
  69.             cin >> tmp;
  70.             mat[y][x] = (tmp == '1');
  71.         }
  72.     }
  73.  
  74.     for (int y = 0; y < m; ++y) {
  75.         for (int x = 0; x < n; ++x) {
  76.             for (int i = 0; i < 4; ++i) {
  77.                 int yy = y + DY[i];
  78.                 int xx = x + DX[i];
  79.  
  80.                 if (isInBounds(yy, xx)) {
  81.                     if (mat[yy][xx]) {
  82.                         ++neighborCnt[y][x];
  83.                     }
  84.                 }
  85.             }
  86.         }
  87.     }
  88.  
  89.     int ans = 0;
  90.  
  91.     for (int y = 0; y < m; ++y) {
  92.         for (int x = 0; x < n; ++x) {
  93.             if (mat[y][x] && !seen[y][x]) {
  94.                 ans += bfs(y, x) ? 1 : 0;
  95.             }
  96.         }
  97.     }
  98.  
  99.     cout << ans << '\n';
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0LkOhB
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!