fork(3) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <list>
  6. #include <climits>
  7. #include <string>
  8. #include <stack>
  9. #include <map>
  10. #include <set>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstring>
  14. #include <cstdlib>
  15. #include <sstream>
  16. #include <iomanip>
  17.  
  18. #define ALL(v) v.begin(), v.end()
  19. #define REP(i, a, b) for(int i = a; i < b; i++)
  20. #define REPD(i, a, b) for(int i = a; i > b; i--)
  21. #define REPLL(i, a, b) for(ll i = a; i < b; i++)
  22. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  23. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  24. #define FORLL(i, a, b) for(ll i = a; i <= b; i++)
  25. #define INF 1000000001
  26.  
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31.  
  32. typedef pair<int, int> pii;
  33. typedef pair<ld, ld> pld;
  34. typedef vector<int>::iterator vit;
  35. typedef set<int>::iterator sit;
  36. typedef vector<int> vi;
  37. typedef vector<pii > vpii;
  38.  
  39. #define pb push_back
  40. #define mp make_pair
  41. #define st first
  42. #define nd second
  43.  
  44. #define EPS 1e-9
  45. #define PI acos(-1.0)
  46. #define MAXN 53
  47.  
  48. int z, n, q;
  49.  
  50. int dx[] = {0, 0, -1, 1, 0, 0};
  51. int dy[] = {1, -1, 0, 0, 0, 0};
  52. int dz[] = {0, 0, 0, 0, 1, -1};
  53.  
  54. int tab[MAXN][MAXN][MAXN];
  55. int vis[MAXN][MAXN][MAXN];
  56. int st[3];
  57. int en[3];
  58.  
  59. int gcd(int a, int b) {
  60.     while(a%=b) swap(a,b);
  61.     return b;
  62. }
  63.  
  64. struct state {
  65.     int x, y, z;
  66.     state(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
  67.     int ok() {
  68.         return x >= 0 && x < n && y >= 0 && y < n && z >= 0 && z < n;
  69.     }
  70.     inline int make_vis() {
  71.         int r = vis[x][y][z];
  72.         vis[x][y][z] = 1;
  73.         return r;
  74.     }
  75.     bool isend() {
  76.         return x == en[0] && y == en[1] && z == en[2];
  77.     }
  78.     void print() {
  79.         cout << x << " " << y << " " << z << endl;
  80.     }
  81. };
  82.  
  83. int bfs(int sta[3]) {
  84.     queue<state> q;
  85.     q.push(state(sta[0], sta[1], sta[2]));
  86.     while(q.size()) {
  87.         state c = q.front(); q.pop();
  88.         if(c.isend()) return true;
  89.         if(c.make_vis()) continue;
  90.         //c.print();
  91.         REP(d, 0, 6) {
  92.             state ns = state(c.x + dx[d], c.y + dy[d], c.z + dz[d]);
  93.             if(!ns.ok()) continue;
  94.             int g = gcd(tab[ns.x][ns.y][ns.z], tab[c.x][c.y][c.z]);
  95.             if(g==1) continue;
  96.             int nx = (c.x + g*dx[d])%n;
  97.             int ny = (c.y + g*dy[d])%n;
  98.             int nz = (c.z + g*dz[d])%n;
  99.             while(nx < 0) nx += n; 
  100.             while(ny < 0) ny += n; 
  101.             while(nz < 0) nz += n; 
  102.             ns = state(nx, ny, nz);
  103.             if(ns.isend()) return true;
  104.             if(ns.ok()) q.push(ns);
  105.         }
  106.     }
  107.     return false;
  108. }
  109.  
  110. int main()
  111. {
  112.     scanf("%d", &z);
  113.     while(z--) {
  114.         scanf("%d%d", &n, &q);
  115.         REP(i, 0, n) REP(j, 0, n) REP(k, 0, n) scanf("%d", &tab[i][j][k]);
  116.         while(q--) {
  117.             scanf("%d%d%d", &st[0], &st[1], &st[2]);
  118.             scanf("%d%d%d", &en[0], &en[1], &en[2]);
  119.             REP(i, 0, n) REP(j, 0, n) REP(k, 0, n) vis[i][j][k] = 0;
  120.             printf(bfs(st) ? "Tak\n" : "Nie\n");
  121.         }
  122.     }
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PlnsML
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!