Cod sursa(job #1779772)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 15 octombrie 2016 16:40:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <utility>
#include <string>

using namespace std;

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

int n, m;
int rx, ry, jx, jy;
char h[102][102];
unsigned short rm[102][102];
unsigned short jm[102][102];

const unsigned short INF = 20000;

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

void citire()
{
    in >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        in.get();
        in.get(h[i]+1, '\n');
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(h[i][j] == 'R')
            {
                rx = i;
                ry = j;
            }
            else if(h[i][j] == 'J')
            {
                jx = i;
                jy = j;
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            rm[i][j] = INF;
            jm[i][j] = INF;
        }
}

void romeo()
{
    queue<pair<short, short> > q;
    q.push(make_pair(rx, ry));
    rm[rx][ry] = 0;
    while(q.empty() == false)
    {
        pair<short, short> p = q.front();
        q.pop();
        for(int k = 0; k < 8; ++k)
        {
            int newx = p.first + dx[k];
            int newy = p.second + dy[k];
            if(h[newx][newy] != 'X' && rm[newx][newy] > rm[p.first][p.second] + 1)
            {
                rm[newx][newy] = rm[p.first][p.second] + 1;
                q.push(make_pair(newx, newy));
            }
        }
    }
}

void julieta()
{
    queue<pair<short, short> > q;
    q.push(make_pair(jx, jy));
    jm[jx][jy] = 0;
    while(q.empty() == false)
    {
        pair<short, short> p = q.front();
        q.pop();
        for(int k = 0; k < 8; ++k)
        {
            int newx = p.first + dx[k];
            int newy = p.second + dy[k];
            if(h[newx][newy] != 'X' && jm[newx][newy] > jm[p.first][p.second] + 1)
            {
                jm[newx][newy] = jm[p.first][p.second] + 1;
                q.push(make_pair(newx, newy));
            }
        }
    }
}

void rezolvare()
{
    romeo();
    julieta();
}

void afisare()
{
    int tmin = INF;
    int x, y;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if(rm[i][j] == jm[i][j] && rm[i][j] < tmin)
            {
                tmin = rm[i][j];
                x = i;
                y = j;
            }
        }
    out << tmin+1 << " " << x << " " << y;
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}