fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const long long INF = 2000000000000000000LL;
  7. const int dx[] = {1, -1, 0, 0};
  8. const int dy[] = {0, 0, 1, -1};
  9. int n, m;
  10. vector<int> par, sz;
  11.  
  12. void make(int val)
  13. {
  14.     par.resize(val + 1);
  15.     sz.resize(val + 1);
  16.     for (int i = 1; i <= val; ++i)
  17.     {
  18.         par[i] = i;
  19.         sz[i] = 1;
  20.     }
  21. }
  22.  
  23. int fi(int v)
  24. {
  25.     if (v == par[v])
  26.         return v;
  27.     return par[v] = fi(par[v]);
  28. }
  29.  
  30. void uni(int u, int v)
  31. {
  32.     int a = fi(u), b = fi(v);
  33.     if (a == b)
  34.         return;
  35.     if (a != b)
  36.     {
  37.         if (sz[a] < sz[b])
  38.             swap(a, b);
  39.         par[b] = a;
  40.         sz[a] += sz[b];
  41.     }
  42. }
  43.  
  44. int ID(int i, int j)
  45. {
  46.     return i * m + j;
  47. }
  48.  
  49. void solve()
  50. {
  51.     cin >> n >> m;
  52.     vector<vector<char>> a(n + 4, vector<char>(m + 4));
  53.     vector<vector<bool>> visited(n + 4, vector<bool>(m + 4, false));
  54.  
  55.     make(n * m + max(n, m));
  56.  
  57.     for (int i = 1; i <= n; ++i)
  58.     {
  59.         for (int j = 1; j <= m; ++j)
  60.         {
  61.             cin >> a[i][j];
  62.             visited[i][j] = false;
  63.         }
  64.     }
  65.  
  66.     for (int i = 1; i <= n; ++i)
  67.     {
  68.         for (int j = 1; j <= m; ++j)
  69.         {
  70.             if (!visited[i][j] && a[i][j] == '#')
  71.             {
  72.                 visited[i][j] = true;
  73.                 queue<pair<int, int>> q;
  74.                 q.push({i, j});
  75.  
  76.                 int u = fi(ID(i, j));
  77.  
  78.                 while (!q.empty())
  79.                 {
  80.                     pair<int, int> h = q.front();
  81.                     q.pop();
  82.  
  83.                     int i1 = h.first, j1 = h.second;
  84.                     for (int k = 0; k < 4; ++k)
  85.                     {
  86.                         int i2 = i1 + dx[k];
  87.                         int j2 = j1 + dy[k];
  88.  
  89.                         if (i2 >= 1 && i2 <= n && j2 >= 1 && j2 <= m && !visited[i2][j2] && a[i2][j2] == '#')
  90.                         {
  91.                             int v = ID(i2, j2);
  92.                             visited[i2][j2] = true;
  93.                             uni(u, v);
  94.                             q.push({i2, j2});
  95.                         }
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.     }
  101.  
  102.     int ans = 0;
  103.  
  104.     for (int i = 1; i <= n; ++i)
  105.     {
  106.         int cnt = 0;
  107.         set<int> s;
  108.         for (int j = 1; j <= m; ++j)
  109.         {
  110.             if (a[i][j] == '.')
  111.                 cnt++;
  112.             if (a[i][j] == '#')
  113.                 s.insert(fi(ID(i, j)));
  114.         }
  115.         if (i - 1 >= 1)
  116.         {
  117.             for (int j = 1; j <= m; ++j)
  118.             {
  119.                 if (a[i - 1][j] == '#')
  120.                     s.insert(fi(ID(i - 1, j)));
  121.             }
  122.         }
  123.         if (i + 1 <= n)
  124.         {
  125.             for (int j = 1; j <= m; ++j)
  126.             {
  127.                 if (a[i + 1][j] == '#')
  128.                     s.insert(fi(ID(i + 1, j)));
  129.             }
  130.         }
  131.  
  132.         for (int x : s)
  133.             cnt += sz[x];
  134.  
  135.         ans = max(ans, cnt);
  136.     }
  137.  
  138.     for (int j = 1; j <= m; ++j)
  139.     {
  140.         int cnt = 0;
  141.         set<int> s;
  142.         for (int i = 1; i <= n; ++i)
  143.         {
  144.             if (a[i][j] == '.')
  145.                 cnt++;
  146.             if (a[i][j] == '#')
  147.                 s.insert(fi(ID(i, j)));
  148.         }
  149.         if (j - 1 >= 1)
  150.         {
  151.             for (int i = 1; i <= n; ++i)
  152.             {
  153.                 if (a[i][j - 1] == '#')
  154.                     s.insert(fi(ID(i, j - 1)));
  155.             }
  156.         }
  157.         if (j + 1 <= m)
  158.         {
  159.             for (int i = 1; i <= n; ++i)
  160.             {
  161.                 if (a[i][j + 1] == '#')
  162.                     s.insert(fi(ID(i, j + 1)));
  163.             }
  164.         }
  165.         for (int x : s)
  166.             cnt += sz[x];
  167.  
  168.         ans = max(ans, cnt);
  169.     }
  170.  
  171.     cout << ans;
  172. }
  173.  
  174. int main()
  175. {
  176.     ios_base::sync_with_stdio(false);
  177.     cin.tie(NULL);
  178.     cout.tie(NULL);
  179.  
  180.     int t;
  181.     cin >> t;
  182.     while (t--)
  183.     {
  184.         solve();
  185.         cout << "\n";
  186.     }
  187.  
  188.     return 0;
  189. }
  190.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
stdout
copy 
1
6
9
11
15
30
https://ideone.com/4ULzPK
language:
C++14 (gcc 8.3)
created:
53 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!