fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // 🛠️ Fix 1: pass comp_id by reference!
  5. int bfs(int row, int col, vector<vector<char>> &graph, vector<vector<int>> &vis,
  6.         vector<vector<int>> &comp_id, int comp, int delrow[], int delcol[], int m, int n) {
  7.  
  8.     queue<pair<int, int>> q;
  9.     q.push({row, col});
  10.     vis[row][col] = 1;
  11.     int size = 0;
  12.  
  13.     while (!q.empty()) {
  14.         auto it = q.front();
  15.         q.pop();
  16.         int r = it.first;
  17.         int c = it.second;
  18.         size++;
  19.         comp_id[r][c] = comp;
  20.         for (int i = 0; i < 4; i++) {
  21.             int nr = r + delrow[i];
  22.             int nc = c + delcol[i];
  23.             if (nr >= 0 && nr < m && nc >= 0 && nc < n && graph[nr][nc] == '#' && !vis[nr][nc]) {
  24.                 q.push({nr, nc});
  25.                 vis[nr][nc] = 1;
  26.             }
  27.         }
  28.     }
  29.     return size;
  30. }
  31.  
  32. int main() {
  33.     int t;
  34.     cin >> t;
  35.     while (t--) {
  36.         int m, n;
  37.         cin >> m >> n;
  38.         vector<vector<char>> graph(m, vector<char>(n));
  39.         for (int i = 0; i < m; i++) {
  40.             for (int j = 0; j < n; j++) {
  41.                 cin >> graph[i][j];
  42.             }
  43.         }
  44.  
  45.         int delrow[] = {-1, 0, 1, 0};
  46.         int delcol[] = {0, -1, 0, 1};
  47.  
  48.         vector<vector<int>> vis(m, vector<int>(n, 0));
  49.         vector<vector<int>> comp_id(m, vector<int>(n, 0));
  50.         unordered_map<int, int> mp;
  51.         int comp = 1;
  52.  
  53.         for (int i = 0; i < m; i++) {
  54.             for (int j = 0; j < n; j++) {
  55.                 if (graph[i][j] == '#' && !vis[i][j]) {
  56.                     int size = bfs(i, j, graph, vis, comp_id, comp, delrow, delcol, m, n);
  57.                     mp[comp] = size;
  58.                     comp++;
  59.                 }
  60.             }
  61.         }
  62.  
  63.         int ans = 0;
  64.  
  65.         // 🔧 Fix 2: Use correct direction arrays (delrow/delcol)
  66.         // setting the rows
  67.         for (int i = 0; i < m; i++) {
  68.             unordered_set<int> st;
  69.             for (int j = 0; j < n; j++) {
  70.                 if (graph[i][j] == '#') continue;
  71.  
  72.                 for (int x = 0; x < 4; x++) {
  73.                     int nrow = i + delrow[x];  // ✅ Corrected
  74.                     int ncol = j + delcol[x];  // ✅ Corrected
  75.                     if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && graph[nrow][ncol] == '#') {
  76.                         st.insert(comp_id[nrow][ncol]);
  77.                     }
  78.                 }
  79.             }
  80.             int count_size = 0;
  81.             for (auto &it : st) {
  82.                 count_size += mp[it];
  83.             }
  84.             ans = max(ans, count_size);
  85.         }
  86.  
  87.         // setting the columns
  88.         for (int j = 0; j < n; j++) {
  89.             unordered_set<int> st;
  90.             for (int i = 0; i < m; i++) {
  91.                 if (graph[i][j] == '#') continue;
  92.  
  93.                 for (int x = 0; x < 4; x++) {
  94.                     int nrow = i + delrow[x];  // ✅ Corrected
  95.                     int ncol = j + delcol[x];  // ✅ Corrected
  96.                     if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && graph[nrow][ncol] == '#') {
  97.                         st.insert(comp_id[nrow][ncol]);
  98.                     }
  99.                 }
  100.             }
  101.             int count_size = 0;
  102.             for (auto &it : st) {
  103.                 count_size += mp[it];
  104.             }
  105.             ans = max(ans, count_size);
  106.         }
  107.  
  108.         for (int i = 0; i < m; i++) {
  109.             for (int j = 0; j < n; j++) {
  110.                 if (graph[i][j] == '#') {
  111.                     ans = max(ans, mp[comp_id[i][j]]);
  112.                 }
  113.             }
  114.         }
  115.  
  116.         cout << ans << endl;
  117.     }
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
stdout
copy 
0
3
5
6
11
25
https://ideone.com/1SvF2w
language:
C++ (gcc 8.3)
created:
6 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!