keker123

Untitled

Feb 17th, 2024
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. #define MAX 1010
  6. using namespace std;
  7.  
  8. string s[MAX];
  9. vector<vector<int> > g;
  10. vector<int> mt, used;
  11.  
  12. int dfs(int v) {
  13.     if (used[v]) return 0;
  14.     used[v] = 1;
  15.     for (int i = 0; i < g[v].size(); i++) {
  16.         int to = g[v][i];
  17.         if (mt[to] == -1 || dfs(mt[to])) {
  18.             mt[to] = v;
  19.             return 1;
  20.         }
  21.     }
  22.     return 0;
  23. }
  24.  
  25. int main() {
  26.     int n, m;
  27.     cin >> n >> m;
  28.  
  29.     for (int i = 0; i < n; i++) {
  30.         cin >> s[i];
  31.     }
  32.  
  33.     g.resize(n * m);
  34.  
  35.     int kl = 0;
  36.     for (int i = 0; i < n; i++) {
  37.         for (int j = 0; j < m; j++) {
  38.  
  39.             if (s[i][j] == '#') continue;
  40.             kl++;
  41.  
  42.             if ((i + j) % 2 == 1) continue;
  43.  
  44.             int u = i * m + j;
  45.  
  46.             if ((j > 0) && (s[i][j - 1] == '.')){
  47.                 g[u].push_back(u - 1);
  48.             }
  49.  
  50.             if ((j < m - 1) && (s[i][j + 1] == '.')) {
  51.                 g[u].push_back(u + 1);
  52.             }
  53.  
  54.             if ((i > 0) && (s[i - 1][j] == '.')) {
  55.                 g[u].push_back(u - m);
  56.             }
  57.  
  58.             if ((i < n - 1) && (s[i + 1][j] == '.')) {
  59.                 g[u].push_back(u + m);
  60.             }
  61.         }
  62.     }
  63.  
  64.     mt = vector<int>(n * m, -1);
  65.     for (int i = 0; i < n; ++i) {
  66.         for (int j = 0; j < m; ++j) {
  67.             if ((i + j) % 2 == 1) continue;
  68.             used = vector<int>(n * m, 0);
  69.             dfs(i*m + j);
  70.         }
  71.     }
  72.  
  73.     int counter = 0;
  74.     for (int i = 0; i < n * m; i++) {
  75.         if (mt[i] != -1) {
  76.             counter++;
  77.         }
  78.     }
  79.  
  80.     if (counter * 2 == kl) {
  81.         cout << "Yes";
  82.     } else {
  83.         cout << "No";
  84.     }
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment