Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <list>
- #include <algorithm>
- #include <string>
- #include <math.h>
- #include <climits>
- #include <queue>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef vector<int> veci;
- typedef vector<bool> vecb;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<bool>> vvb;
- const int INF_I = 1e9;
- const ll INF_LL = 1e18;
- int n, m;
- vector<vector<pi>> p;
- vvb used;
- vector<vector<char>> vec;
- int x_1, y_1, x_2, y_2;
- //bool bfs(int v_x, int v_y) {
- // vvb used(n, vecb(m));
- // used[v_x][v_y] = true;
- // queue<pi> q;
- // q.emplace(mp(v_x, v_y));
- // while (!q.empty()) {
- // int a = q.front().x;
- // int b = q.front().y;
- // q.pop();
- // if ((a == x1 && b == y1) || (a == x2 || b == y2))
- // continue;
- // for (int i = -1; i <= 1; i++)
- // for (int j = -1; j <= 1; j++)
- // if (i * i + j * j == 1)
- // if (a + i < n && a + i > 0 && b + j > 0 && b + j < m) {
- //
- // }
- //
- //
- // }
- //}
- bool dfs(int v_x, int v_y) {
- if (used[v_x][v_y])
- return false;
- used[v_x][v_y] = 1;
- for (int i = -1; i <= 1; i++)
- for (int j = -1; j <= 1; j++)
- if (i * i + j * j == 1) {
- int a = v_x + i, b = v_y + j;
- if (a < n && a >= 0 && b >= 0 && b < m)
- if (vec[a][b] == 0 && (p[a][b].x == -1 || dfs(p[a][b].x, p[a][b].y))){
- p[v_x + i][v_y + j] = mp(v_x, v_y);
- return true;
- }
- }
- return false;
- }
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m;
- cin >> x_1 >> y_1 >> x_2 >> y_2;
- x_1--, x_2--, y_1--, y_2--;
- bool color = 1;
- vec.assign(n, vector<char>(m));
- p.assign(n, vector<pi>(m, mp(-1, -1)));
- int cnt = 0;
- vvb used1(n, vecb(m));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- vec[i][j] = color;
- color = !color;
- }
- color = !vec[i][0];
- }
- vec[x_1][y_1] = 2;
- vec[x_2][y_2] = 2;
- for (int i = 0; i < n; i++) {
- char f = vec[i][0];
- for (int j = 0; j < m; j++) {
- if (vec[i][j] == 0) {
- if (f == 0 && j + 1 < m && vec[i][j+1] == 1) {
- p[i][j] = mp(i, j + 1);
- used1[i][j + 1] = true;
- cnt++;
- }
- else if (f == 1 && j - 1 >= 0 && vec[i][j - 1] == 1) {
- p[i][j] = mp(i, j - 1);
- used1[i][j - 1] = true;
- cnt++;
- }
- }
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++)
- if (vec[i][j] == 1 && !used1[i][j]) {
- used.assign(n, vecb(m, 0));
- cnt += dfs(i, j);
- }
- }
- cout << (cnt * 2 == m*n-2 ? "YES" : "NO") << endl;
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment