Guest User

Untitled

a guest
Jan 17th, 2020
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. struct ver
  6. {
  7.     bool color;
  8.     int val;
  9.  
  10. };
  11. ver d[102];
  12. int n;
  13. bool flag = false;
  14.  
  15. void DFS(int u)
  16. {
  17.     if (flag == false)
  18.     {
  19.         if (u == n * n)
  20.         {
  21.             flag = true;
  22.         }
  23.         d[u].color = true;
  24.         if (d[u].val % 2 == 1)
  25.         {
  26.             if ((u - n >= 1) && (d[u - n].color == false))
  27.                 DFS(u - n);
  28.             d[u].val--;
  29.         }
  30.         if (d[u].val >= 8)
  31.         {
  32.             if ((u - 1 >= 1) && ((u - 1) % n != 0) && (d[u - 1].color == false))
  33.                 DFS(u - 1);
  34.             d[u].val = d[u].val - 8;
  35.         }
  36.         if ((d[u].val == 2 || d[u].val == 6))
  37.         {
  38.             if ((u + n <= n * n) && (d[u + n].color == false))
  39.                 DFS(u + n);
  40.             d[u].val = d[u].val - 2;
  41.         }
  42.         if (d[u].val == 4)
  43.         {
  44.             if ((u % n != 0) && (d[u + 1].color == false))
  45.                 DFS(u + 1);
  46.             d[u].val = d[u].val - 4;
  47.         }
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     freopen("input.txt", "r", stdin);
  54.     freopen("output.txt", "w", stdout);
  55.  
  56.     cin >> n;
  57.     for (int i = 1; i <= n * n; i++)
  58.     {
  59.         d[i].color = false;
  60.         cin >> d[i].val;
  61.     }
  62.     DFS(1);
  63.     if (flag == true)
  64.         cout << "Yes";
  65.     else
  66.         cout << "No";
  67.  
  68.     return 0;
  69. }
RAW Paste Data