Raslboyy

111663

Nov 27th, 2019
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <algorithm>
  5. #include <string>
  6. #include <math.h>
  7. #include <climits>
  8. #include <queue>
  9.  
  10. //#include <chrono>
  11. //#include <fstream>
  12. //#include <bits/stdc++.h>
  13.  
  14. #define mp make_pair
  15. #define pb push_back
  16. #define eb emplace_back
  17. #define x first
  18. #define y second
  19. #define sz(x) (int)x.size()
  20. #define all(x) begin(x), end(x)
  21. #define rall(x) rbegin(x), rend(x)
  22. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  23. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  24.  
  25. using namespace std;
  26.  
  27. typedef unsigned long long ull;
  28. typedef long long ll;
  29. typedef long double ld;
  30. typedef pair<int, int> pi;
  31. typedef pair<ll, ll> pl;
  32. typedef vector<int> veci;
  33. typedef vector<bool> vecb;
  34. typedef vector<vector<int>> vvi;
  35. typedef vector<vector<bool>> vvb;
  36.  
  37. const int INF_I = 1e9;
  38. const ll INF_LL = 1e18;
  39.  
  40. int n, m;
  41.  
  42. vector<vector<pi>> p;
  43. vvb used;
  44. vector<vector<char>> vec;
  45. int x_1, y_1, x_2, y_2;
  46.  
  47. //bool bfs(int v_x, int v_y) {
  48. //  vvb used(n, vecb(m));
  49. //  used[v_x][v_y] = true;
  50. //  queue<pi> q;
  51. //  q.emplace(mp(v_x, v_y));
  52. //  while (!q.empty()) {
  53. //      int a = q.front().x;
  54. //      int b = q.front().y;
  55. //      q.pop();
  56. //      if ((a == x1 && b == y1) || (a == x2 || b == y2))
  57. //          continue;
  58. //      for (int i = -1; i <= 1; i++)
  59. //          for (int j = -1; j <= 1; j++)
  60. //              if (i * i + j * j == 1)
  61. //                  if (a + i < n && a + i > 0 && b + j > 0 && b + j < m) {
  62. //
  63. //                  }
  64. //             
  65. //                 
  66. //  }
  67. //}
  68.  
  69. bool dfs(int v_x, int v_y) {
  70.     if (used[v_x][v_y])
  71.         return false;
  72.     used[v_x][v_y] = 1;
  73.     for (int i = -1; i <= 1; i++)
  74.         for (int j = -1; j <= 1; j++)
  75.             if (i * i + j * j == 1) {
  76.                 int a = v_x + i, b = v_y + j;
  77.                 if (a < n && a >= 0 && b >= 0 && b < m)
  78.                     if (vec[a][b] == 0 && (p[a][b].x == -1 || dfs(p[a][b].x, p[a][b].y))){
  79.                         p[v_x + i][v_y + j] = mp(v_x, v_y);
  80.                         return true;
  81.                     }
  82.             }
  83.     return false;
  84. }
  85.  
  86.  
  87. int main() {
  88.     /*ifstream cin("in.txt");
  89.     ofstream cout("out.txt");
  90.     auto start_time = chrono::high_resolution_clock::now();*/
  91.  
  92.     ios::sync_with_stdio(false);
  93.     cin.tie(0);
  94.     cout.tie(0);
  95.  
  96.    
  97.     cin >> n >> m;
  98.    
  99.     cin >> x_1 >> y_1 >> x_2 >> y_2;
  100.     x_1--, x_2--, y_1--, y_2--;
  101.  
  102.     bool color = 1;
  103.     vec.assign(n, vector<char>(m));
  104.     p.assign(n, vector<pi>(m, mp(-1, -1)));
  105.     int cnt = 0;
  106.     vvb used1(n, vecb(m));
  107.     for (int i = 0; i < n; i++) {
  108.         for (int j = 0; j < m; j++) {
  109.             vec[i][j] = color;
  110.             color = !color;
  111.         }
  112.         color = !vec[i][0];
  113.     }
  114.     vec[x_1][y_1] = 2;
  115.     vec[x_2][y_2] = 2;
  116.  
  117.     for (int i = 0; i < n; i++) {
  118.         char f = vec[i][0];
  119.         for (int j = 0; j < m; j++) {
  120.             if (vec[i][j] == 0) {
  121.                 if (f == 0 && j + 1 < m && vec[i][j+1] == 1) {
  122.                     p[i][j] = mp(i, j + 1);
  123.                     used1[i][j + 1] = true;
  124.                     cnt++;
  125.                 }
  126.                 else if (f == 1 && j - 1 >= 0 && vec[i][j - 1] == 1) {
  127.                     p[i][j] = mp(i, j - 1);
  128.                     used1[i][j - 1] = true;
  129.                     cnt++;
  130.                 }
  131.             }
  132.         }
  133.     }
  134.  
  135.     for (int i = 0; i < n; i++) {
  136.         for (int j = 0; j < m; j++)
  137.             if (vec[i][j] == 1 && !used1[i][j]) {
  138.                 used.assign(n, vecb(m, 0));
  139.                 cnt += dfs(i, j);
  140.             }
  141.     }
  142.    
  143.     cout << (cnt * 2 == m*n-2 ? "YES" : "NO") << endl;
  144.  
  145.     /*auto end_time = chrono::high_resolution_clock::now();
  146.     chrono::duration<double> duration = end_time - start_time;
  147.     cout << duration.count() << "\n";
  148.     cin.close();
  149.     cout.close();*/
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment