Advertisement
K_Y_M_bl_C

Untitled

Oct 2nd, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. //#define _GLIBCXX_DEBUG
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<int> vi;
  10. typedef long double ld;
  11.  
  12. #define mk make_pair
  13. #define inb push_back
  14. #define X first
  15. #define Y second
  16. #define all(v) v.begin(), v.end()
  17. #define sqr(x) (x) * (x)
  18. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  19. #define y1 AYDARBOG
  20. //continue break pop_back return size_t
  21.  
  22. int solve();
  23.  
  24. int main()
  25. {
  26.     //ios_base::sync_with_stdio(0);
  27.     //cin.tie(0);
  28. #define TASK "html"
  29. #ifndef _DEBUG
  30.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  31. #endif
  32.     solve();
  33. #ifdef _DEBUG
  34.     fprintf(stderr, "\nTIME: %.3f\n", TIME);
  35. #endif
  36. }
  37.  
  38. const int BUFSZ = (int)1e5 + 7;
  39. char buff[BUFSZ];
  40. string get_str()
  41. {
  42.     scanf(" %s", buff);
  43.     return string(buff);
  44. }
  45.  
  46. struct edge
  47. {
  48.     int to, f, c;
  49.     edge() {};
  50.     edge(int to, int f, int c) : to(to), f(f), c(c) {};
  51. };
  52.  
  53. const int INF = (int)1e9 + 7;
  54.  
  55. struct Dinic
  56. {
  57.     int n;
  58.     vector<edge> e;
  59.     vector<vi> g;
  60.     vi p, d;
  61.     int s, t;
  62.     Dinic() {};
  63.     Dinic(int _n)
  64.     {
  65.         n = _n;
  66.         g.resize(n);
  67.         s = 0, t = n - 1;
  68.     }
  69.     void add_edge(int x, int y, int c = 1)
  70.     {
  71.         g[x].inb(e.size());
  72.         e.inb(edge(y, 0, c));
  73.         g[y].inb(e.size());
  74.         e.inb(edge(x, 0, 0));
  75.     }
  76.     int bfs()
  77.     {
  78.         queue<int> q;
  79.         d.assign(n, INF);
  80.         d[s] = 0;
  81.         int ans = 0;
  82.         q.push(s);
  83.         while (!q.empty())
  84.         {
  85.             int u = q.front();
  86.             q.pop();
  87.             for (int ne : g[u])
  88.             {
  89.                 int to = e[ne].to;
  90.                 int f = e[ne].f;
  91.                 int c = e[ne].c;
  92.                 if (d[to] != INF || f >= c)
  93.                     continue;
  94.                 ans |= (to == t);
  95.                 d[to] = d[u] + 1;
  96.                 q.push(to);
  97.             }
  98.         }
  99.         return ans;
  100.     }
  101.     int dfs(int u, int minc)
  102.     {
  103.         if (u == t || !minc)
  104.             return minc;
  105.         for (size_t i = p[u]; i < g[u].size(); ++i)
  106.         {
  107.             int ne = g[u][i];
  108.             int to = e[ne].to;
  109.             int f = e[ne].f;
  110.             int c = e[ne].c;
  111.             if (d[u] + 1 != d[to])
  112.                 continue;
  113.             int delta = dfs(to, min(minc, c - f));
  114.             if (delta)
  115.             {
  116.                 e[ne].f += delta;
  117.                 e[ne ^ 1].f -= delta;
  118.                 return delta;
  119.             }
  120.             ++p[u];
  121.         }
  122.         return 0;
  123.     }
  124.     int getMaxFlow()
  125.     {
  126.         int ans = 0;
  127.         while (bfs())
  128.         {
  129.             p.assign(n, 0);
  130.             int flow = dfs(s, INF);
  131.             while (flow)
  132.             {
  133.                 ans += flow;
  134.                 flow = dfs(s, INF);
  135.             }
  136.         }
  137.         return ans;
  138.     }
  139. };
  140.  
  141. int solve()
  142. {
  143.     int n, m;
  144.     scanf("%d %d", &n, &m);
  145.     Dinic G(n * m + 2);
  146.     char a[n][m + 1];
  147.     for (int i = 0; i < n; ++i)
  148.     {
  149.         scanf(" %s", a[i]);
  150.     }
  151.     int fr = n * m;
  152.     for (int i = 0; i < n; ++i)
  153.     {
  154.         for (int j = 0; j < m; ++j)
  155.         {
  156.             if (a[i][j] == '#')
  157.             {
  158.                 --fr;
  159.                 continue;
  160.             }
  161.             if ((i + j) & 1)
  162.             {
  163.                 G.add_edge(i * m + j, n * m + 1);
  164.             }
  165.             else
  166.             {
  167.                 G.add_edge(0, i * m + j);
  168.             }
  169.         }
  170.     }
  171.     vi dx = { -1, 0, 1, 0 };
  172.     vi dy = { 0, -1, 0, 1 };
  173.     for (int x = 0; x < n; ++x)
  174.     {
  175.         for (int y = x & 1; y < m; y += 2)
  176.         {
  177.             if (a[x][y] == '#')
  178.                 continue;
  179.             for (int id = 0; id < 4; ++id)
  180.             {
  181.                 int nx = x + dx[id];
  182.                 int ny = y + dy[id];
  183.                 if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == '#')
  184.                     continue;
  185.                 G.add_edge(x * m + y, nx * m + ny);
  186.             }
  187.         }
  188.     }
  189.     int mxflow = G.getMaxFlow();
  190.     puts((mxflow * 2 == fr) ? "Yes" : "No");
  191.     return 0;
  192. }
  193. close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement