fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4.  
  5. int gcd(int a, int b) {
  6.     return b == 0 ? a : gcd(b, a % b);
  7. }
  8.  
  9. int lcm(int a, int b) {
  10.     return (a == 0 || b == 0) ? 0 : (a / gcd(a, b)) * b;
  11. }
  12.  
  13. vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  14. vector<string> graph;
  15. vector<vector<int>> vis;
  16.  
  17. int cc, rmx, rmn, cmx, cmn;
  18.  
  19. void dfs(int r, int c) {
  20.     if (vis[r][c] || graph[r][c] == '.') {
  21.         return;
  22.     }
  23.     vis[r][c] = 1;
  24.     cc++;
  25.     rmx = max(rmx, r);
  26.     rmn = min(rmn, r);
  27.     cmx = max(cmx, c);
  28.     cmn = min(cmn, c);
  29.  
  30.     for (auto dir : directions) {
  31.         int nr = r + dir[0];
  32.         int nc = c + dir[1];
  33.         if (nr >= 0 && nr < graph.size() && nc >= 0 && nc < graph[0].size()) {
  34.             dfs(nr, nc);
  35.         }
  36.     }
  37. }
  38.  
  39. int main() {
  40.  
  41.  
  42.     int t;
  43.     cin >> t;
  44.     while (t--) {
  45.         int n, m;
  46.         cin >> n >> m;
  47.         graph.assign(n, "");
  48.         vis.assign(n, vector<int>(m, 0));
  49.         vector<int> emr(n, 0), emc(m, 0);
  50.  
  51.         for (int i = 0; i < n; i++) {
  52.             cin >> graph[i];
  53.             for (int j = 0; j < m; j++) {
  54.                 if (graph[i][j] == '.') {
  55.                     emr[i]++;
  56.                     emc[j]++;
  57.                 }
  58.             }
  59.         }
  60.  
  61.         vector<int> mpr(n + 1, 0), mpc(m + 1, 0);
  62.         for (int i = 0; i < n; i++) {
  63.             for (int j = 0; j < m; j++) {
  64.                 if (vis[i][j] || graph[i][j] == '.') continue;
  65.                 cc = 0;
  66.                 rmx = rmn = i;
  67.                 cmx = cmn = j;
  68.                 dfs(i, j);
  69.  
  70.                 rmn = max(rmn - 1, 0);
  71.                 rmx = min(rmx + 1, n - 1);
  72.                 cmn = max(cmn - 1, 0);
  73.                 cmx = min(cmx + 1, m - 1);
  74.                 mpr[rmn] += cc;
  75.                 mpr[rmx + 1] -= cc;
  76.                 mpc[cmn] += cc;
  77.                 mpc[cmx + 1] -= cc;
  78.             }
  79.         }
  80.  
  81.         int ans = INT_MIN;
  82.         for (int i = 0; i < n; i++) {
  83.             if (i > 0) mpr[i] += mpr[i - 1];
  84.             ans = max(ans, mpr[i] + emr[i]);
  85.         }
  86.  
  87.         for (int i = 0; i < m; i++) {
  88.             if (i > 0) mpc[i] += mpc[i - 1];
  89.             ans = max(ans, mpc[i] + emc[i]);
  90.         }
  91.  
  92.         cout << ans << endl;
  93.     }
  94. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
1
4 2
..
#.
#.
.#
stdout
copy 
6
https://ideone.com/M6mVfQ
language:
C++ (gcc 8.3)
created:
2 hours 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!