Guest User

Untitled

a guest
May 21st, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.45 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #pragma comment(linker, "/STACK:268435456")
  4.  
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cmath>
  8. #include <cstdio>
  9. #include <cstring>
  10. #include <deque>
  11. #include <iostream>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <string>
  17. #include <vector>
  18.  
  19. using namespace std;
  20.  
  21. //const string IN_NAME = "input.txt";
  22. //const string OUT_NAME = "output.txt";
  23.  
  24. const string NAME = "cube";
  25. const string IN_NAME = NAME + ".in";
  26. const string OUT_NAME = NAME + ".out";
  27.  
  28. template<class T> T abs(T &x)       { return ((x) >= 0) ? (x) : (-(x)); }
  29. template<class T> T sqr(T &x)       { return (x) * (x); }
  30. template<class T> T min(T &a, T &b) { return ((a) < (b)) ? (a) : (b); }
  31. template<class T> T max(T &a, T &b) { return ((a) > (b)) ? (a) : (b); }
  32.  
  33. #define sz(v) ((int) ((v).size()))
  34. #define all(v) (v).begin(), (v).end()
  35. #define fori(i,n) for (int i = 0; i < (n); i++)
  36. #define show(x) { cout << (#x) << " = " << (x) << endl; }
  37.  
  38. typedef long long ll;
  39. typedef pair<int, int> ii;
  40.  
  41. //------------------------------------------------------------------------------
  42.  
  43. int n;
  44. char a[20][20][20];
  45. char b[20][20];
  46. bool v[20][20][20];
  47.  
  48. /*
  49. void rotate1() {
  50.     for (int k = 0; k < n; k++) {
  51.         for (int i = 0; i < n; i++) {
  52.             for (int j = 0; j < n; j++) {
  53.                 b[i][j] = a[n-1-j][i][k];
  54.             }
  55.         }
  56.         for (int i = 0; i < n; i++) {
  57.             for (int j = 0; j < n; j++) {
  58.                 a[i][j][k] = b[i][j];
  59.             }
  60.         }
  61.     }
  62. }
  63.  
  64. void rotate2() {
  65.     for (int j = 0; j < n; j++) {
  66.         for (int i = 0; i < n; i++) {
  67.             for (int k = 0; k < n; k++) {
  68.                 b[i][k] = a[n-1-k][j][i];
  69.             }
  70.         }
  71.         for (int i = 0; i < n; i++) {
  72.             for (int k = 0; k < n; k++) {
  73.                 a[i][j][k] = b[i][k];
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. void rotate3() {
  80.     for (int i = 0; i < n; i++) {
  81.         for (int j = 0; j < n; j++) {
  82.             for (int k = 0; k < n; k++) {
  83.                 b[j][k] = a[i][n-1-k][j];
  84.             }
  85.         }
  86.         for (int j = 0; j < n; j++) {
  87.             for (int k = 0; k < n; k++) {
  88.                 a[i][j][k] = b[j][k];
  89.             }
  90.         }
  91.     }
  92. }
  93. */
  94.  
  95. bool good(int x, int y, int z) {
  96.     return (x >= 0 && x < n) && (y >= 0 && y < n) && (z >= 0 && z < n);
  97. }
  98.    
  99. const int dx[6] = {1,-1,0,0,0,0};
  100. const int dy[6] = {0,0,1,-1,0,0};
  101. const int dz[6] = {0,0,0,0,1,-1};
  102.  
  103. void dfs(int x, int y, int z) {
  104.     v[x][y][z] = true;
  105.     for (int k = 0; k < 6; k++) {
  106.         int nx = x + dx[k];
  107.         int ny = y + dy[k];
  108.         int nz = z + dz[k];
  109.         if (good(nx, ny, nz) && !v[nx][ny][nz] && a[nx][ny][nz] == a[x][y][z]) {
  110.             dfs(nx, ny, nz);
  111.         }
  112.     }
  113. }
  114.  
  115. bool tryMoveOutIJ0(int x, int y) {
  116.     memset(v, 0, sizeof(v));
  117.     dfs(x, y, 0);
  118.     for (int i = 0; i < n; i++) {
  119.         for (int j = 0; j < n; j++) {
  120.             for (int k = 1; k < n; k++) {
  121.                 if (v[i][j][k]) {
  122.                     if (a[i][j][k-1] != a[i][j][k]) {
  123.                         return false;
  124.                     }
  125.                 }
  126.             }
  127.         }
  128.     }
  129.     return true;
  130. }
  131.  
  132. bool tryMoveOutIJN(int x, int y) {
  133.     memset(v, 0, sizeof(v));
  134.     dfs(x, y, n-1);
  135.     for (int i = 0; i < n; i++) {
  136.         for (int j = 0; j < n; j++) {
  137.             for (int k = n-2; k >= 0; k--) {
  138.                 if (v[i][j][k]) {
  139.                     if (a[i][j][k+1] != a[i][j][k]) {
  140.                         return false;
  141.                     }
  142.                 }
  143.             }
  144.         }
  145.     }
  146.     return true;
  147. }
  148.  
  149. bool tryMoveOutIK0(int x, int z) {
  150.     memset(v, 0, sizeof(v));
  151.     dfs(x, 0, z);
  152.     for (int i = 0; i < n; i++) {
  153.         for (int j = 1; j < n; j++) {
  154.             for (int k = 0; k < n; k++) {
  155.                 if (v[i][j][k]) {
  156.                     if (a[i][j-1][k] != a[i][j][k]) {
  157.                         return false;
  158.                     }
  159.                 }
  160.             }
  161.         }
  162.     }
  163.     return true;
  164. }
  165.  
  166. bool tryMoveOutIKN(int x, int z) {
  167.     memset(v, 0, sizeof(v));
  168.     dfs(x, n-1, z);
  169.     for (int i = 0; i < n; i++) {
  170.         for (int j = n-2; j >= 0; j--) {
  171.             for (int k = 0; k < n; k++) {
  172.                 if (v[i][j][k]) {
  173.                     if (a[i][j+1][k] != a[i][j][k]) {
  174.                         return false;
  175.                     }
  176.                 }
  177.             }
  178.         }
  179.     }
  180.     return true;
  181. }
  182.  
  183. bool tryMoveOutJK0(int y, int z) {
  184.     memset(v, 0, sizeof(v));
  185.     dfs(0, y, z);
  186.     for (int i = 1; i < n; i++) {
  187.         for (int j = 0; j < n; j++) {
  188.             for (int k = 0; k < n; k++) {
  189.                 if (v[i][j][k]) {
  190.                     if (a[i-1][j][k] != a[i][j][k]) {
  191.                         return false;
  192.                     }
  193.                 }
  194.             }
  195.         }
  196.     }
  197.     return true;
  198. }
  199.  
  200. bool tryMoveOutJKN(int y, int z) {
  201.     memset(v, 0, sizeof(v));
  202.     dfs(n-1, y, z);
  203.     for (int i = n-2; i >= 0; i--) {
  204.         for (int j = 0; j < n; j++) {
  205.             for (int k = 0; k < n; k++) {
  206.                 if (v[i][j][k]) {
  207.                     if (a[i+1][j][k] != a[i][j][k]) {
  208.                         return false;
  209.                     }
  210.                 }
  211.             }
  212.         }
  213.     }
  214.     return true;
  215. }
  216.  
  217. bool solveTest() {
  218.     for (int i = 0; i < n; i++)
  219.         for (int j = 0; j < n; j++)
  220.             if (tryMoveOutIJ0(i, j))
  221.                 return true;
  222.     for (int i = 0; i < n; i++)
  223.         for (int j = 0; j < n; j++)
  224.             if (tryMoveOutIJN(i, j))
  225.                 return true;
  226.     for (int i = 0; i < n; i++)
  227.         for (int k = 0; k < n; k++)
  228.             if (tryMoveOutIK0(i, k))
  229.                 return true;
  230.     for (int i = 0; i < n; i++)
  231.         for (int k = 0; k < n; k++)
  232.             if (tryMoveOutIKN(i, k))
  233.                 return true;
  234.     for (int j = 0; j < n; j++)
  235.         for (int k = 0; k < n; k++)
  236.             if (tryMoveOutJK0(j, k))
  237.                 return true;
  238.     for (int j = 0; j < n; j++)
  239.         for (int k = 0; k < n; k++)
  240.             if (tryMoveOutJKN(j, k))
  241.                 return true;
  242.     return false;
  243. }
  244.  
  245. int main()
  246. {
  247. #ifndef ONLINE_JUDGE
  248.     freopen(IN_NAME.c_str(), "r", stdin);
  249.     freopen(OUT_NAME.c_str(), "w", stdout);
  250. #endif
  251.  
  252.     int tests;
  253.     cin >> tests;
  254.     for (int t = 1; t <= tests; t++) {
  255.         cin >> n;
  256.         for (int i = 0; i < n; i++) {
  257.             for (int j = 0; j < n; j++) {
  258.                 string s;
  259.                 cin >> s;
  260.                 for (int k = 0; k < n; k++) {
  261.                     a[i][j][k] = s[k];
  262.                 }
  263.             }
  264.         }
  265.         if (n > 1 && solveTest()) {
  266.             cout << "No" << endl;
  267.         } else {
  268.             cout << "Yes" << endl;
  269.         }
  270.     }
  271. }
Add Comment
Please, Sign In to add comment