Cod sursa(job #1543274)

Utilizator HuskyezTarnu Cristian Huskyez Data 6 decembrie 2015 10:15:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <fstream>
#include <string>
#include <queue>
#include <climits>

using namespace std;

ifstream in("rj.in");
ofstream out("rj.out");

struct pct
{
    int x; int y;
}initr, initj, tempj, tempr, now, fin;

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

queue<pct> ro;
queue<pct> ju;

string s[105];
int n, m;
int distr[105][105];
int distj[105][105];

int tmin = INT_MAX;
int l, c;

bool verif(pct p)
{
    if(p.x > n or p.x < 1 or p.y < 0 or p.y > m-1)
        return false;
    return true;
}

void romeo()
{
    while(!ro.empty())
    {
        for(int i=0; i<8; i++)
        {
            now.x = tempr.x + dx[i];
            now.y = tempr.y + dy[i];
            if(distr[now.x][now.y] == 0 and verif(now)==true)
            {
                ro.push(now);
                distr[now.x][now.y] = distr[tempr.x][tempr.y] + 1;
            }
        }
        ro.pop();
        tempr = ro.front();
    }
}

void julieta()
{
    while(!ju.empty())
    {
        for(int i=0; i<8; i++)
        {
            now.x = tempj.x + dx[i];
            now.y = tempj.y + dy[i];
            if(distj[now.x][now.y] == 0 and verif(now)==true)
            {
                ju.push(now);
                distj[now.x][now.y] = distj[tempj.x][tempj.y] + 1;
            }
        }
        ju.pop();
        tempj = ju.front();
    }
}

int main()
{
    in >> n >> m;

    for(int i=0; i<=n; i++)
        getline(in, s[i]);

    for(int i=1; i<=n; i++)
        for(int j=0; j<m; j++)
        {
            if(s[i][j] == 'R')
            {
               initr.x = i;
               initr.y = j;
               distr[i][j] = 1;
            }
            if(s[i][j] == 'J')
            {
               initj.x = i;
               initj.y = j;
               distj[i][j] = 1;
            }
            if(s[i][j] == 'X')
            {
                distj[i][j] = -1;
                distr[i][j] = -1;
            }
        }

    ro.push(initr);
    tempr = ro.front();
    ju.push(initj);
    tempj = ju.front();

    romeo();
    julieta();

    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(distr[i][j] == distj[i][j] and distr[i][j] > 0 and distj[i][j] > 0)
            {
                if(tmin > distr[i][j])
                {
                    tmin = distr[i][j]; l = i; c = j+1;
                }
                if(tmin == distr[i][j])
                {
                    if(l > i)
                    {
                        l = i; c = j+1;
                    }
                    if(l == i)
                        if(c > j+1)
                        {
                            c = j+1;
                        }
                }
            }
        }
    }
    out << tmin << ' ' << l << ' ' << c;

    return 0;
}