Josif_tepe

Untitled

Mar 14th, 2026
304
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <cstring>
  5. using namespace std;
  6.  
  7. const int di[4] = {-1, 1, 0, 0};
  8. const int dj[4] = {0, 0, -1, 1};
  9.  
  10.  
  11.  
  12. int bfs(int n, int m, vector<string> & v) {
  13.     bool visited[n][m];
  14.     int res = 0;
  15.     memset(visited, false, sizeof visited);
  16.     for(int i = 0; i < n; i++) {
  17.         for(int j = 0; j < m; j++) {
  18.             if(!visited[i][j] and v[i][j] == '.') {
  19.                 queue<int> q;
  20.                 q.push(i);
  21.                 q.push(j);
  22.                 res++;
  23.                
  24.                 while(!q.empty()) {
  25.                     int ci = q.front(); q.pop();
  26.                     int cj = q.front(); q.pop();
  27.                    
  28.                     for(int k = 0; k < 4; k++) {
  29.                         int ti = ci + di[k];
  30.                         int tj = cj + dj[k];
  31.                        
  32.                         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and v[ti][tj] == '.') {
  33.                             q.push(ti);
  34.                             q.push(tj);
  35.                             visited[ti][tj] = true;
  36.                         }
  37.                     }
  38.                    
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     return res;
  44. }
  45. int main(){
  46.     ios_base::sync_with_stdio(false);
  47.     int n, m;
  48.     cin >> n >> m;
  49.     char mat[n][m];
  50.    
  51.     for(int i = 0; i < n; i++) {
  52.         for(int j = 0; j < m; j++) {
  53.             cin >> mat[i][j];
  54.         }
  55.     }
  56.    
  57.     int res = 2e9;
  58.     for(int R = 0; R < n; R++) {
  59.         vector<string> v;
  60.         for(int i = 0; i < n; i++) {
  61.             if(i != R) {
  62.                 string tmp = "";
  63.                 for(int j = 0; j < m; j++) {
  64.                     tmp += mat[i][j];
  65.                 }
  66.                 v.push_back(tmp);
  67.             }
  68.         }
  69.         res = min(res, bfs(n - 1, m, v));
  70.        
  71.        
  72.     }
  73.  
  74.     for(int C = 0; C < m; C++) {
  75.         vector<string> v;
  76.         for(int i = 0; i < n; i++) {
  77.             string tmp = "";
  78.             for(int j = 0; j < m; j++) {
  79.                 if(j != C) {
  80.                     tmp += mat[i][j];
  81.                 }
  82.             }
  83.             v.push_back(tmp);
  84.            
  85.            
  86.         }
  87.         res = min(res, bfs(n, m - 1, v));
  88.     }
  89.    
  90.     cout << res << endl;
  91.     return 0;
  92. }
  93.  
Advertisement
Add Comment
Please, Sign In to add comment