fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int bfs(int row, int col,
  5.         vector<vector<char>>& graph,
  6.         vector<vector<int>>& vis,
  7.         vector<vector<int>>& comp_id,   
  8.         int comp,
  9.         int delrow[], int delcol[],
  10.         int m, int n)
  11. {
  12.     queue<pair<int,int>> q;
  13.     q.push({row,col});
  14.     vis[row][col] = 1;
  15.     int size = 0;
  16.  
  17.     while (!q.empty()) {
  18.         auto [r, c] = q.front();
  19.         q.pop();
  20.         size++;
  21.         comp_id[r][c] = comp;          
  22.  
  23.         for (int i = 0; i < 4; ++i) {
  24.             int nr = r + delrow[i];
  25.             int nc = c + delcol[i];
  26.             if (nr >= 0 && nr < m && nc >= 0 && nc < n
  27.                 && graph[nr][nc] == '#'
  28.                 && !vis[nr][nc])
  29.             {
  30.                 q.push({nr, nc});
  31.                 vis[nr][nc] = 1;
  32.             }
  33.         }
  34.     }
  35.     return size;
  36. }
  37.  
  38. int main() {
  39.     ios::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.  
  42.     int t;
  43.     cin >> t;
  44.     while (t--) {
  45.         int m, n;
  46.         cin >> m >> n;
  47.  
  48.         vector<vector<char>> graph(m, vector<char>(n));
  49.         for (int i = 0; i < m; ++i)
  50.             for (int j = 0; j < n; ++j)
  51.                 cin >> graph[i][j];
  52.  
  53.         int delrow[] = {-1, 0, 1, 0};
  54.         int delcol[] = { 0,-1, 0, 1};
  55.  
  56.         vector<vector<int>> vis(m, vector<int>(n, 0));
  57.         vector<vector<int>> comp_id(m, vector<int>(n, 0));
  58.         unordered_map<int,int> comp_size;
  59.  
  60.         int comp = 1;
  61.         for (int i = 0; i < m; ++i)
  62.             for (int j = 0; j < n; ++j)
  63.                 if (graph[i][j] == '#' && !vis[i][j]) {
  64.                     int sz = bfs(i, j, graph, vis, comp_id,
  65.                                  comp, delrow, delcol, m, n);
  66.                     comp_size[comp++] = sz;
  67.                 }
  68.  
  69.         int ans = 0;                                   
  70.  
  71.         // evaluate each row
  72.         for (int i = 0; i < m; ++i) {
  73.             unordered_set<int> st;
  74.             int x=0;
  75.             for (int j = 0; j < n; ++j) {
  76.                 if (graph[i][j] == '#') st.insert(comp_id[i][j]);
  77.                 if (i - 1 >= 0)        st.insert(comp_id[i-1][j]);
  78.                 if (i + 1 <  m)        st.insert(comp_id[i+1][j]);
  79.                 if(graph[i][j]=='.') x++;
  80.             }
  81.             int cur = 0;
  82.             for (int id : st) cur += comp_size[id];
  83.             ans = max(ans, cur+x);
  84.         }
  85.  
  86.         // evaluate each column
  87.         for (int j = 0; j < n; ++j) {
  88.             unordered_set<int> st;
  89.             int x=0;
  90.             for (int i = 0; i < m; ++i) {
  91.                 if (graph[i][j] == '#') st.insert(comp_id[i][j]);
  92.                 if (j - 1 >= 0)        st.insert(comp_id[i][j-1]);
  93.                 if (j + 1 <  n)        st.insert(comp_id[i][j+1]);
  94.                 if(graph[i][j]=='.') x++;
  95.             }
  96.             int cur = 0;
  97.             for (int id : st) cur += comp_size[id];
  98.             ans = max(ans, cur+x);
  99.         }
  100.         cout << ans << '\n';
  101.     }
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 5284KB
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/DAkh6T
language:
C++ (gcc 8.3)
created:
10 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!