USACO-T035: The Tamworth Two

/*
ID: mickyta1
TASK: ttwo
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;

const pii dir[4] = {pii(-1, 0), pii(0, 1), pii(1, 0), pii(0, -1)}; // N E S W
const int N = 10 + 5;

deque<pii> mvCycle[2];
vector<pii> mvNoCycle[2];
int row, col;
char board[N][N];
bool visited[N][N][4];

int __lcm(int a, int b){
    return a / __gcd(a, b) * b;
}

void BFS(pii st, int i){
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            for(int d = 0; d < 4; ++d){
                visited[i][j][d] = false;
            }
        }
    }
    queue<ppi> que;
    visited[st.f][st.s][0] = true;
    que.emplace(st, 0);
    while(!que.empty()){
        pii u = que.front().f;
        int ud = que.front().s;
        que.pop();
        mvCycle[i].emplace_back(u.f * row + u.s, ud);
        pii v = pii(u.f + dir[ud].f, u.s + dir[ud].s);
        int vd = ud;
        if(board[v.f][v.s] == '*'){
            v = u;
            vd = (ud + 1) % 4;
        }
        if(!visited[v.f][v.s][vd]){
            visited[v.f][v.s][vd] = true;
            que.emplace(v, vd);
        } else {
            pii tr = pii(v.f * row + v.s, vd);
            while(!mvCycle[i].empty() && mvCycle[i].front() != tr){
                mvNoCycle[i].push_back(mvCycle[i].front());
                mvCycle[i].pop_front();
            }
        }
    }
}

int main(){
    freopen("ttwo.in", "r", stdin);
    freopen("ttwo.out", "w", stdout);

    row = 10;
    col = 10;
    for(int i = 1; i <= row; ++i){
        board[i][0] = '*';
        board[i][col + 1] = '*';
    }
    for(int j = 1; j <= col; ++j){
        board[0][j] = '*';
        board[row + 1][j] = '*';
    }
    pii stCow, stFarmer;
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            scanf(" %c", &board[i][j]);
            if(board[i][j] == 'C'){
                stCow = pii(i, j);
            } else if(board[i][j] == 'F'){
                stFarmer = pii(i, j);
            }
        }
    }
    BFS(stCow, 0);
    BFS(stFarmer, 1);
    int f = 0;
    int s = 1;
    if(mvNoCycle[f].size() < mvNoCycle[s].size()){
        swap(f, s);
    }
    for(int i = 0; i < mvNoCycle[f].size(); ++i){
        if(i < mvNoCycle[s].size() && mvNoCycle[f][i].f == mvNoCycle[s][i].f ||
           i >= mvNoCycle[s].size() && mvNoCycle[f][i].f == mvCycle[s][(i - mvNoCycle[s].size()) % mvCycle[s].size()].f){
            cout << i << '\n';
            fclose(stdin);
            fclose(stdout);
            return 0;
        }
    }
    int mn = 1e9;
    int lcm = __lcm(mvCycle[f].size(), mvCycle[s].size());
    int sBase = (int)mvNoCycle[f].size() - mvNoCycle[s].size();
    for(int i = 0; i < mvCycle[f].size(); ++i){
        for(int j = 0; j < lcm && i + j < mn; j += mvCycle[f].size()){
            if(mvCycle[f][i].f == mvCycle[s][(sBase + i + j) % mvCycle[s].size()].f){
                mn = min(mn, (int)mvNoCycle[f].size() + i + j);
            }
        }
    }
    if(mn == 1e9){
        cout << "0\n";
    } else {
        cout << mn << '\n';
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}