Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#define _GLIBCXX_DEBUG
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef long double ld;
- #define mk make_pair
- #define inb push_back
- #define X first
- #define Y second
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- #define TIME 1.0 * clock() / CLOCKS_PER_SEC
- #define y1 AYDARBOG
- //continue break pop_back return size_t
- int solve();
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- #define TASK "html"
- #ifndef _DEBUG
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- #ifdef _DEBUG
- fprintf(stderr, "\nTIME: %.3f\n", TIME);
- #endif
- }
- const int BUFSZ = (int)1e5 + 7;
- char buff[BUFSZ];
- string get_str()
- {
- scanf(" %s", buff);
- return string(buff);
- }
- struct edge
- {
- int to, f, c;
- edge() {};
- edge(int to, int f, int c) : to(to), f(f), c(c) {};
- };
- const int INF = (int)1e9 + 7;
- struct Dinic
- {
- int n;
- vector<edge> e;
- vector<vi> g;
- vi p, d;
- int s, t;
- Dinic() {};
- Dinic(int _n)
- {
- n = _n;
- g.resize(n);
- s = 0, t = n - 1;
- }
- void add_edge(int x, int y, int c = 1)
- {
- g[x].inb(e.size());
- e.inb(edge(y, 0, c));
- g[y].inb(e.size());
- e.inb(edge(x, 0, 0));
- }
- int bfs()
- {
- queue<int> q;
- d.assign(n, INF);
- d[s] = 0;
- int ans = 0;
- q.push(s);
- while (!q.empty())
- {
- int u = q.front();
- q.pop();
- for (int ne : g[u])
- {
- int to = e[ne].to;
- int f = e[ne].f;
- int c = e[ne].c;
- if (d[to] != INF || f >= c)
- continue;
- ans |= (to == t);
- d[to] = d[u] + 1;
- q.push(to);
- }
- }
- return ans;
- }
- int dfs(int u, int minc)
- {
- if (u == t || !minc)
- return minc;
- for (size_t i = p[u]; i < g[u].size(); ++i)
- {
- int ne = g[u][i];
- int to = e[ne].to;
- int f = e[ne].f;
- int c = e[ne].c;
- if (d[u] + 1 != d[to])
- continue;
- int delta = dfs(to, min(minc, c - f));
- if (delta)
- {
- e[ne].f += delta;
- e[ne ^ 1].f -= delta;
- return delta;
- }
- ++p[u];
- }
- return 0;
- }
- int getMaxFlow()
- {
- int ans = 0;
- while (bfs())
- {
- p.assign(n, 0);
- int flow = dfs(s, INF);
- while (flow)
- {
- ans += flow;
- flow = dfs(s, INF);
- }
- }
- return ans;
- }
- };
- int solve()
- {
- int n, m;
- scanf("%d %d", &n, &m);
- Dinic G(n * m + 2);
- char a[n][m + 1];
- for (int i = 0; i < n; ++i)
- {
- scanf(" %s", a[i]);
- }
- int fr = n * m;
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (a[i][j] == '#')
- {
- --fr;
- continue;
- }
- if ((i + j) & 1)
- {
- G.add_edge(i * m + j, n * m + 1);
- }
- else
- {
- G.add_edge(0, i * m + j);
- }
- }
- }
- vi dx = { -1, 0, 1, 0 };
- vi dy = { 0, -1, 0, 1 };
- for (int x = 0; x < n; ++x)
- {
- for (int y = x & 1; y < m; y += 2)
- {
- if (a[x][y] == '#')
- continue;
- for (int id = 0; id < 4; ++id)
- {
- int nx = x + dx[id];
- int ny = y + dy[id];
- if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == '#')
- continue;
- G.add_edge(x * m + y, nx * m + ny);
- }
- }
- }
- int mxflow = G.getMaxFlow();
- puts((mxflow * 2 == fr) ? "Yes" : "No");
- return 0;
- }
- close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement