Cod sursa(job #1750315)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 29 august 2016 21:42:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.31 kb
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

#define in "rj.in"
#define out "rj.out"
#define NMAX (100 + 7)
#define pb push_back

using namespace std;
int n, m, check, sol, dirX[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1}, dirY[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
char mat[NMAX][NMAX], ch, matJ[NMAX][NMAX], matR[NMAX][NMAX];
struct punct
{
    int X;
    int Y;
} pj, pr;
struct stare
{
    punct pt;
    int pas;
    bool operator <(const stare &ax) const
    {
        if(pt.X < ax.pt.X) return 1;
        if(pt.X > ax.pt.X) return 0;
        if(pt.Y < ax.pt.Y) return 1;
        return 0;
    }
} ans;
queue <stare> Romeo, Julieta, helper;
vector <stare> R, J;

inline void spinR()
{
    //printf("spinR\n");
    while(!Romeo.empty())
    {
        stare tmp = Romeo.front(), aux;
        if(tmp.pas > sol) break;
        Romeo.pop();
        aux.pas = tmp.pas + 1;
        for(int i = 1; i<= 8; ++i)
        {
            aux.pt.X = tmp.pt.X + dirX[i];
            aux.pt.Y = tmp.pt.Y + dirY[i];
            if(matR[aux.pt.X][aux.pt.Y] == 1) continue;
            matR[aux.pt.X][aux.pt.Y] = 1;
            Romeo.push(aux);
        }
    }
}
inline void spinJ()
{
    //printf("spinJ\n");
    while(!Julieta.empty())
    {
        stare tmp = Julieta.front(), aux;
        if(tmp.pas > sol) break;
        Julieta.pop();
        aux.pas = tmp.pas + 1;
        for(int i = 1; i<= 8; ++i)
        {
            aux.pt.X = tmp.pt.X + dirX[i];
            aux.pt.Y = tmp.pt.Y + dirY[i];
            if(matJ[aux.pt.X][aux.pt.Y] == 1) continue;
            matJ[aux.pt.X][aux.pt.Y] = 1;
            Julieta.push(aux);
        }
    }
}
bool Verificare()
{
    J.clear();
    R.clear();
    //printf("check %d\n", sol);
    stare tmp;
    while(!Romeo.empty())
    {
        tmp = Romeo.front();
        Romeo.pop();
        //printf("R %d %d\n", tmp.pt.X, tmp.pt.Y);
        helper.push(tmp);
        R.pb(tmp);
    }
    while(!helper.empty())
    {
        tmp = helper.front();
        helper.pop();
        Romeo.push(tmp);
    }
    while(!Julieta.empty())
    {
        tmp = Julieta.front();
        Julieta.pop();
        //printf("J %d %d\n", tmp.pt.X, tmp.pt.Y);
        helper.push(tmp);
        J.pb(tmp);
    }
    while(!helper.empty())
    {
        tmp = helper.front();
        helper.pop();
        Julieta.push(tmp);
    }
    sort(R.begin(), R.end());
    sort(J.begin(), J.end());
    int itR = 0, itJ = 0, sze1 = R.size(), sze2 = J.size();
    while(itR < sze1 && itJ < sze2)
    {
        if(R[itR] < J[itJ]) itR ++;
        else if(J[itJ] < R[itR]) itJ ++;
        else
        {
            //printf("check %d %d\n", R[itR].pt.X, R[itR].pt.Y);
            //printf("check %d %d\n", J[itJ].pt.X, J[itJ].pt.Y);
            ans = R[itR];
            return 1;
        }
    }
    return 0;
}

inline void citire()
{
    scanf("%d %d", &n, &m);
    scanf("%c", &ch);
    for(int i = 1; i<= n; ++i)
    {
        fgets(mat[i]+1, NMAX-1, stdin);
    }
}
inline void build()
{
    for(int i = 1; i<= n; ++i)
    {
        for(int j = 1; j<= m; ++j)
        {
            if(mat[i][j] == 'R')
            {
                pr.X = i;
                pr.Y = j;
            }
            if(mat[i][j] == 'J')
            {
                pj.X = i;
                pj.Y = j;
            }
            if(mat[i][j] == 'X')
            {
                matJ[i][j] = 1;
                matR[i][j] = 1;
            }
        }
    }
    for(int i = 0; i<= n+1; ++i)
    {
        matR[i][m+1] = matJ[i][m+1] = matR[i][0] = matJ[i][0] = 1;
    }
    for(int i = 0; i<= m+1; ++i)
    {
        matR[0][i] = matJ[0][i] = matR[n+1][i] = matJ[n+1][i] = 1;
    }
}
inline void solve()
{
    stare tmp;
    tmp.pt = pr;
    tmp.pas = 0;
    Romeo.push(tmp);
    tmp.pt = pj;
    Julieta.push(tmp);
    matR[pr.X][pr.Y] = 1;
    matJ[pj.X][pj.Y] = 1;
    while(1)
    {
        spinR(); /// ok
        spinJ(); /// ok
        if(Verificare()) break; /// ok
        sol++;
    }
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    citire(); /// ok
    build(); /// ok
    solve();
    printf("%d %d %d\n", ans.pas+1, ans.pt.X, ans.pt.Y);
    return 0;
}