Cod sursa(job #2097513)

Utilizator UWantMyNameGheorghe Vlad Camil UWantMyName Data 31 decembrie 2017 17:52:42
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>
#define in "rj.in"
#define out "rj.out"
#define oo 1000000
using namespace std;
ifstream fin(in);
ofstream fout(out);

int n,m,xr,yr,xj,yj;
int dr[105][105];
int dj[105][105];
char a[105][105];
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={-1,1,0,0,-1,1,1,-1};
queue <pair<int,int> > q;

void Citire()
{
    int i,j;

    fin >> n >> m;
    fin.get();
    for (i = 1; i <= n; i++)
    {
        fin.getline(a[i]+1,105);
        for (j = 1; j <= m; j++)
            if (a[i][j] == 'R')
            {
                xr = i;
                yr = j;
            }
            else if (a[i][j] == 'J')
            {
                xj = i;
                yj = j;
            }
    }
}

void Bordare()
{
    int i;

    for (i = 0;i <= m + 1; i++) a[0][i] = a[n+1][i] = 'X';
    for (i = 0;i <= n + 1; i++) a[i][0] = a[i][m+1] = 'X';
}

void Init()
{
    int i,j;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            dj[i][j] = dr[i][j] = oo;
}

void Lee_R()
{
    int i,j,x,y,k;

    q.push({xr,yr});
    dr[xr][yr] = 1;
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (dr[x][y] > dr[i][j] + 1 && a[x][y] != 'X')
            {
                dr[x][y] = dr[i][j] + 1;
                q.push({x,y});
            }
        }
    }
}

void Lee_J()
{
    int i,j,x,y,k;

    q.push({xj,yj});
    dj[xj][yj] = 1;
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (dj[x][y] > dj[i][j] + 1 && a[x][y] != 'X')
            {
                dj[x][y] = dj[i][j] + 1;
                q.push({x,y});
            }
        }
    }
}

void Intalnire()
{
    int i,j,mini,poz1,poz2;

    mini = oo;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(dr[i][j] == dj[i][j] && mini > dr[i][j])
            {
                mini = dr[i][j];
                poz1 = i;
                poz2 = j;
            }
    fout << mini << " " << poz1 << " " << poz2 << "\n";
}

int main()
{
    Citire();
    Bordare();
    Init();
    Lee_R();
    Lee_J();
    Intalnire();

    fin.close();
    fout.close();
    return 0;
}