Cod sursa(job #1288202)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 8 decembrie 2014 17:58:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct Pozitii
{
    short x, y, t;
} w, w1, q[10002];


char a[102][102];
short b[102][102], n, m, rx, ry;
short c[102][102], jx, jy;
short dx[] = {-1, 1, 0, 0,-1,-1, 1, 1};
short dy[] = { 0, 0, 1,-1,-1, 1, 1,-1};

void Lee_Romeo();
void Lee_Julieta();
void Cautare();

int main()
{
    int i, j;
    fin >> n >> m;
    fin.get();
    for (i = 1; i <= n; i++)
        fin.getline(a[i] + 1, 101);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (a[i][j] == 'R') { rx = i; ry = j; }
            else if (a[i][j] == 'J') { jx = i; jy = j; }
    for (i = 0; i <= n+1; i++)
        a[i][0] = a[i][m+1] = 'X';
    for (j = 0; j <= m+1; j++)
        a[0][j] = a[n+1][j] = 'X';
    Lee_Romeo();
    Lee_Julieta();
    Cautare();
    fin.close();
    fout.close();
    return 0;
}

void Lee_Romeo()
{
    int pr, ul, k;
    pr = ul = 0;
    w.x = rx;
    w.y = ry;
    w.t = 1;
    q[0] = w;
    b[w.x][w.y] = 1;
    while (pr <= ul)
    {
        w = q[pr];
        pr++;
        for (k = 0; k < 8; k++)
        {
            w1.x = w.x + dx[k];
            w1.y = w.y + dy[k];
            w1.t = w.t + 1;
            if (a[w1.x][w1.y] == ' ' &&
                (!b[w1.x][w1.y] || w.t + 1 < b[w1.x][w1.y]))
            {
                ul++;
                q[ul] = w1;
                b[w1.x][w1.y] = w1.t;
            }
        }
    }
}

void Lee_Julieta()
{
    int pr, ul, k;
    pr = ul = 0;
    w.x = jx;
    w.y = jy;
    w.t = 1;
    q[0] = w;
    while (pr <= ul)
    {
        w = q[pr];
        pr++;
        for (k = 0; k < 8; k++)
        {
            w1.x = w.x + dx[k];
            w1.y = w.y + dy[k];
            w1.t = w.t + 1;
            if (a[w1.x][w1.y] == ' ' &&
                (!c[w1.x][w1.y] || w.t + 1 < c[w1.x][w1.y]))
            {
                ul++;
                q[ul] = w1;
                c[w1.x][w1.y] = w1.t;
            }
        }
    }
}

void Cautare()
{
    int i, j, xf, yf, minim = 999999;
    xf = yf = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (b[i][j] == c[i][j] && c[i][j] < minim && b[i][j])
                { minim = b[i][j]; xf = i; yf = j; }
    fout << minim << " " << xf << " " << yf << " \n";
}