Cod sursa(job #2059636)

Utilizator moltComan Calin molt Data 7 noiembrie 2017 12:15:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 102,M = 102;

struct comp
{
    int l,c;
};
comp vecin,curent,start;
comp q[N * M];

char a[N][M];

const int dl[] = {-1,-1,-1,0,1,1,1,0};
const int dc[] = {-1,0,1,1,1,0,-1,-1};

int n,m,mat[N][M],xr,yr,xj,yj;

void bordare()
{
    for (int i = 0; i <= n + 1; ++i)
        mat[i][0] = mat[i][m + 1] = -1;
    for (int j = 0; j <= m + 1; ++j)
        mat[0][j] = mat[n + 1][j] = -1;
}

void romeo()
{
    int p = 0,u = -1;
    start.l = xr;
    start.c = yr;
    mat[start.l][start.c] = 1;
    q[++u] = start;
    while (p <= u)
    {
        curent = q[p++];
        for (int i = 0; i < 8; ++i)
        {
            vecin.l = curent.l + dl[i];
            vecin.c = curent.c + dc[i];
            if (mat[vecin.l][vecin.c] == 0)
            {
                ++u;
                q[u].l = vecin.l;
                q[u].c = vecin.c;
                mat[vecin.l][vecin.c] = mat[curent.l][curent.c] + 1;
            }
        }
    }
}

int mat2[N][M];

void julieta()
{
    for (int i = 0; i <= n + 1; ++i)
        mat2[i][0] = mat2[i][m + 1] = -1;
    for (int j = 0; j <= m + 1; ++j)
        mat2[0][j] = mat2[n + 1][j] = -1;
    int p = 0,u = -1;
    start.l = xj;
    start.c = yj;
    mat2[start.l][start.c] = 1;
    q[++u] = start;
    while (p <= u)
    {
        curent = q[p++];
        for (int i = 0; i < 8; ++i)
        {
            vecin.l  = curent.l + dl[i];
            vecin.c  = curent.c + dc[i];
            if (mat2[vecin.l][vecin.c] == 0)
            {
                q[++u] = vecin;
                mat2[vecin.l][vecin.c] = mat2[curent.l][curent.c] + 1;
            }
        }

    }
}

int main()
{
    in>>n>>m;
    in.get();
    for (int i = 1; i <= n; ++i)
        in.getline(1 + a[i],M);


    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == ' ')
            {
                mat[i][j] = 0;
                mat2[i][j] = 0;
            }
            if (a[i][j] == 'X')
            {
                mat[i][j] = -1;
                mat2[i][j] = -1;
            }
            if (a[i][j] == 'R')
            {
                xr = i;
                yr = j;
            }
            if (a[i][j] == 'J')
            {
                xj = i;
                yj = j;
            }
        }
    bordare();
    romeo();
    julieta();
   /* for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            out<<mat[i][j]<<" ";
        out<<"\n";
    }
    out<<endl;
     for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            out<<mat2[i][j]<<" ";
        out<<"\n";
    }*/
    //for (int i = 1; i <= n; ++i)
    //{
    //for (int j = 1; j <= m; ++j)
    //out<<a[i][j];
    //  out << (1 + a[i]);
    //out<<"\n";
    //}
    int min = 1000,cmin,lmin;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            if (mat[i][j] == mat2[i][j] && mat[i][j] > 0 && mat[i][j] < min)
                {min = mat[i][j];
                lmin = i;
                cmin = j;}
        out<<min<<" "<<lmin<<" "<<cmin;
    return 0;
}