Advertisement
mickypinata

USACO-T035: The Tamworth Two

Dec 15th, 2021
685
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: ttwo
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define f first
  11. #define s second
  12. typedef pair<int, int> pii;
  13. typedef pair<pii, int> ppi;
  14.  
  15. const pii dir[4] = {pii(-1, 0), pii(0, 1), pii(1, 0), pii(0, -1)}; // N E S W
  16. const int N = 10 + 5;
  17.  
  18. deque<pii> mvCycle[2];
  19. vector<pii> mvNoCycle[2];
  20. int row, col;
  21. char board[N][N];
  22. bool visited[N][N][4];
  23.  
  24. int __lcm(int a, int b){
  25.     return a / __gcd(a, b) * b;
  26. }
  27.  
  28. void BFS(pii st, int i){
  29.     for(int i = 1; i <= row; ++i){
  30.         for(int j = 1; j <= col; ++j){
  31.             for(int d = 0; d < 4; ++d){
  32.                 visited[i][j][d] = false;
  33.             }
  34.         }
  35.     }
  36.     queue<ppi> que;
  37.     visited[st.f][st.s][0] = true;
  38.     que.emplace(st, 0);
  39.     while(!que.empty()){
  40.         pii u = que.front().f;
  41.         int ud = que.front().s;
  42.         que.pop();
  43.         mvCycle[i].emplace_back(u.f * row + u.s, ud);
  44.         pii v = pii(u.f + dir[ud].f, u.s + dir[ud].s);
  45.         int vd = ud;
  46.         if(board[v.f][v.s] == '*'){
  47.             v = u;
  48.             vd = (ud + 1) % 4;
  49.         }
  50.         if(!visited[v.f][v.s][vd]){
  51.             visited[v.f][v.s][vd] = true;
  52.             que.emplace(v, vd);
  53.         } else {
  54.             pii tr = pii(v.f * row + v.s, vd);
  55.             while(!mvCycle[i].empty() && mvCycle[i].front() != tr){
  56.                 mvNoCycle[i].push_back(mvCycle[i].front());
  57.                 mvCycle[i].pop_front();
  58.             }
  59.         }
  60.     }
  61. }
  62.  
  63. int main(){
  64.     freopen("ttwo.in", "r", stdin);
  65.     freopen("ttwo.out", "w", stdout);
  66.  
  67.     row = 10;
  68.     col = 10;
  69.     for(int i = 1; i <= row; ++i){
  70.         board[i][0] = '*';
  71.         board[i][col + 1] = '*';
  72.     }
  73.     for(int j = 1; j <= col; ++j){
  74.         board[0][j] = '*';
  75.         board[row + 1][j] = '*';
  76.     }
  77.     pii stCow, stFarmer;
  78.     for(int i = 1; i <= row; ++i){
  79.         for(int j = 1; j <= col; ++j){
  80.             scanf(" %c", &board[i][j]);
  81.             if(board[i][j] == 'C'){
  82.                 stCow = pii(i, j);
  83.             } else if(board[i][j] == 'F'){
  84.                 stFarmer = pii(i, j);
  85.             }
  86.         }
  87.     }
  88.     BFS(stCow, 0);
  89.     BFS(stFarmer, 1);
  90.     int f = 0;
  91.     int s = 1;
  92.     if(mvNoCycle[f].size() < mvNoCycle[s].size()){
  93.         swap(f, s);
  94.     }
  95.     for(int i = 0; i < mvNoCycle[f].size(); ++i){
  96.         if(i < mvNoCycle[s].size() && mvNoCycle[f][i].f == mvNoCycle[s][i].f ||
  97.            i >= mvNoCycle[s].size() && mvNoCycle[f][i].f == mvCycle[s][(i - mvNoCycle[s].size()) % mvCycle[s].size()].f){
  98.             cout << i << '\n';
  99.             fclose(stdin);
  100.             fclose(stdout);
  101.             return 0;
  102.         }
  103.     }
  104.     int mn = 1e9;
  105.     int lcm = __lcm(mvCycle[f].size(), mvCycle[s].size());
  106.     int sBase = (int)mvNoCycle[f].size() - mvNoCycle[s].size();
  107.     for(int i = 0; i < mvCycle[f].size(); ++i){
  108.         for(int j = 0; j < lcm && i + j < mn; j += mvCycle[f].size()){
  109.             if(mvCycle[f][i].f == mvCycle[s][(sBase + i + j) % mvCycle[s].size()].f){
  110.                 mn = min(mn, (int)mvNoCycle[f].size() + i + j);
  111.             }
  112.         }
  113.     }
  114.     if(mn == 1e9){
  115.         cout << "0\n";
  116.     } else {
  117.         cout << mn << '\n';
  118.     }
  119.  
  120.     fclose(stdin);
  121.     fclose(stdout);
  122.     return 0;
  123. }
  124.  
Advertisement
RAW Paste Data Copied
Advertisement