pastebin

Paste Search Dynamic
Recent pastes
getDivisors
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5.  
  6. bool isPrime(ll n) {
  7.     for (ll i = 2; i * i <= n; i++)
  8.         if (n % i == 0)
  9.             return false;
  10.     return true;
  11. }
  12. vector <ll> getDivisors(ll n) {
  13.     vector <ll> divs;
  14.     divs.push_back(1);
  15.     for (ll i = 2; i * i <= n; i++) {
  16.         if (n % i == 0) {
  17.             divs.push_back(i);
  18.             if (i != n / i) divs.push_back(n / i);
  19.         }
  20.     }
  21.     divs.push_back(n);
  22.     return divs;
  23. }
  24. vector<pair<ll, ll>> factorize(ll n) {
  25.     vector<pair<ll, ll>> fact;
  26.     for (ll i = 2; i * i <= n; i++) {
  27.         int cnt = 0;
  28.         while (n % i == 0) {
  29.             n /= i;
  30.             cnt++;
  31.         }
  32.         if (cnt) fact.emplace_back(i, cnt);
  33.     }
  34.     if (n > 1) fact.emplace_back(n, 1);
  35.     return fact;
  36. }
  37. vector<bool> sieve(ll n) {
  38.     vector<bool>isPrime(n + 1, true);
  39.     isPrime[0] = isPrime[1] = false;
  40.     for (ll i = 2; i <= n; i++)
  41.         if (isPrime[i])
  42.             for (ll j = 2 * i; j <= n; j += i)
  43.                 isPrime[j] = false;
  44.     return isPrime;
  45. }
  46. void WhAt_ThE_BuG()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.     cout.tie(nullptr);
  51. }
  52. ll fastPower(ll base, ll power)
  53. {
  54.     if (power == 0)
  55.         return 1;
  56.     ll result = fastPower(base, power / 2);
  57.     result *= result;
  58.     if (power & 1)
  59.         result = result * power;
  60.     return result;
  61. }
  62. ll GCD(ll a, ll b)
  63. {
  64.     if (b == 0)
  65.         return a;
  66.     return GCD(b, a % b);
  67. }
  68. ll LCM(ll a, ll b)
  69. {
  70.     return a * b / GCD(a, b);
  71. }
  72. string reverse(string r)
  73. {
  74.     for (int i = 0; i < r.size() / 2; i++)
  75.     {
  76.         swap(r[i], r[r.size() - i - 1]);
  77.     }
  78.     return r;
  79. }
  80.  
  81. bool palindrome(string ans) {
  82.     if (ans == reverse(ans))
  83.         return true;
  84.     return false;
  85. }
  86. int const S = 1e2 + 10;
  87.  
  88. int n, m;
  89. vector<vector<int>> adj;
  90. int arrX[] = { 0,0,1,1,-1,1,-1,-1 };
  91. int arrY[] = { 1,-1,1,-1,1,0,0,-1 };
  92. int dis[26][26];
  93. int grid[26][26];
  94. int sizee = 0;
  95. void bfs(int x, int y)
  96. {
  97.     queue<pair<int, int>> qe;
  98.     qe.push({ x,y });
  99.     dis[x][y] = 0;
  100.     sizee++;
  101.     while (!qe.empty())
  102.     {
  103.         int x1 = qe.front().first, y1 = qe.front().second;
  104.         qe.pop();
  105.         for (int i = 0; i < 8; i++)
  106.         {
  107.             int x2 = x1 + arrX[i], y2 = y1 + arrY[i];
  108.             if (x2 > 0 && x2 <= n && y2 > 0 && y2 <= m)
  109.             {
  110.                 if (grid[x2][y2]==1&&dis[x2][y2]==1e9)
  111.                 {
  112.                     sizee++;
  113.                     dis[x2][y2] = 1;
  114.                     qe.push({ x2,y2 });
  115.  
  116.                 }
  117.             }
  118.         }
  119.     }
  120. }
  121.  
  122. int main() {
  123.  
  124.     WhAt_ThE_BuG();
  125.     int t;
  126.     cin >> t;
  127.     bool print = false;
  128.     if(t>1) print = true;
  129.     while (t--)
  130.     {
  131.         string s;
  132.         cin >> s;
  133.         for (int i = 1; i <= s.size(); i++) {
  134.             if (i != 1)
  135.                 cin >> s;
  136.  
  137.             for (int j = 1; j <= s.size(); j++)
  138.             {
  139.                 grid[i][j] = s[j - 1] - '0';
  140.             }
  141.         }
  142.  
  143.         n = m = s.size();
  144.         for (int i = 1; i <= n; i++) {
  145.             for (int j = 1; j <= m; j++) {
  146.                 dis[i][j] = 1e9;
  147.             }
  148.         }
  149.         int ans = 0;
  150.         for (int i = 1; i <= n; i++) {
  151.             for (int j = 1; j <= m; j++)
  152.             {
  153.                 if (grid[i][j] == 1 && dis[i][j] == 1e9) {
  154.                     bfs(i, j);
  155.                     ans = max(ans, sizee);
  156.                     sizee = 0;
  157.                 }
  158.             }
  159.         }
  160.         cout << ans;
  161.         if(print && t) cout<<endl<<endl;
  162.     }
  163.  
  164.  
  165. }
Parsed in 0.022 seconds