Cod sursa(job #2671864)

Utilizator robertnanu_fmiNanu Robert-Ionut robertnanu_fmi Data 12 noiembrie 2020 19:20:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

short v[101][101], m, n, i, j, xj[10009], yj[10009], xr[10009], yr[10009];
short dx[]= {-1,-1,-1,0,0,1,1,1}, dy[]= {-1,0,1,-1,1,-1,0,1}, p, u, k, small = 32000;

bool viz1[101][101], viz2[101][101];
char s[101];
short mim1[101][101], mim2[101][101], xs, ys;

bool inside(int x, int y)
{
    return x <= n && y <= m && x => 1 && y => 1; //daca e in matrice
}
void lee1()
{
    u = 1;
    p = 0;
    viz1[xr[1]][yr[1]] = 1; //exact ca un dfs
    while(p <= u)
    {
        ++p;
        for(k = 0; k < 8; ++k)
        {
            if(inside(xr[p] + dx[k], yr[p] + dy[k]))
            {
                if(!viz1[xr[p] + dx[k]][yr[p] + dy[k]])
                {
                    if(!v[xr[p] + dx[k]][yr[p] + dy[k]])
                    {
                        ++u;
                        xr[u] = xr[p] + dx[k]; //vecinul
                        yr[u]=yr[p] + dy[k];
                        viz1[xr[u]][yr[u]] = 1; //il vizitez si pe el
                        mim1[xr[u]][yr[u]] = mim1[xr[p]][yr[p]] + 1; //calculez drumul
                    }
                }
            }
        }
    }
}
void lee2()
{
    u = 1;
    p = 0;
    viz2[xj[1]][yj[1]] = 1;
    while(p<=u)
    {
        ++p;
        for(k = 0; k < 8; ++k)
        {
            if(inside(xj[p] + dx[k], yj[p] + dy[k]))
            {
                if(!viz2[xj[p] + dx[k]][yj[p] + dy[k]])
                {
                    if(!v[xj[p] + dx[k]][yj[p] + dy[k]])
                    {
                        ++u;
                        xj[u] = xj[p] + dx[k];
                        yj[u] = yj[p] + dy[k];
                        viz2[xj[u]][yj[u]] = 1;
                        mim2[xj[u]][yj[u]] = mim2[xj[p]][yj[p]] + 1;
                    }
                }
            }
        }
    }
}
int main()
{
    f >> n >> m;
    f.get();
    for(i = 1; i <= n; ++i)
    {
        f.getline(s + 1, 110);
        for(j = 1; j <= m; ++j)
        {
            if(s[j] == 'R')
            {
                xr[1] = i;
                yr[1] = j;
            }
            if(s[j] == 'J')
            {
                xj[1] = i;
                yj[1] = j;
            }
            if(s[j] == 'X')
                v[i][j] = 1;
        }
    }
    lee1();
    lee2();
    for(i = 1; i <= n; ++i)
    {
        for(j = 1; j <= m; ++j)
        {
            if(mim1[i][j] == mim2[i][j] && mim1[i][j] < small && mim1[i][j])
            {
                xs = i; //pozitia de intalnire
                ys = j;
                small = mim1[i][j]; //meet in the middle
            }
        }
    }
    g<<small+1<<' '<<xs<<' '<<ys;
    return 0;
}