Cod sursa(job #2860907)

Utilizator david_octavianoctavian david_octavian Data 3 martie 2022 10:51:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <fstream>
#include <cstring>
using namespace std;

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

const int NMAX = 101;
int a[NMAX + 5][NMAX + 5];
int b[NMAX + 5][NMAX + 5];
int c[NMAX + 5][NMAX + 5];

struct RJ
{
    int x , y;
};
RJ q[NMAX * NMAX + 5];
int dx[] = {-1 , 0 , 1 , 0 , -1 , 1 , 1 , -1};
int dy[] = {0 , 1, 0 , -1 , -1 , 1 , -1 , 1};
int n , m , xr , yr , xj ,yj;
char line[101];
int main()
{
    RJ aux , aux1;
    int p , u;
    cin >> n >> m;
    cin.get();
    for(int i = 1; i <= n; i++)
    {
        cin.getline(line , 101);
        for(int j = 0; j < m; j++)
        {
            if(line[j] == 'X')
                a[i][j + 1] = -1;
            else
                if(line[j] == 'R')
            {
                xr = i;
                yr = j + 1;
            }
            else
                if(line[j] == 'J')
            {
                xj = i;
                yj = j + 1;
            }
        }
    }
    for(int j = 0 ; j <= m + 1; j++)
        a[0][j] = a[n + 1][j] = -1;
    for(int i = 0; i <= n + 1; i++)
        a[i][0] = a[i][m + 1] = -1;
    memcpy(b , a , sizeof(a));
    memcpy(c , a , sizeof(a));
    aux.x = xr;
    aux.y = yr;
    b[xr][yr] = 1;
    p = u = 1;
    q[u] = aux;
    while(p <= u)
    {
        aux = q[p];
        p++;
        for(int i = 0; i < 8; i++)
        {
            aux1.x = aux.x + dx[i];
            aux1.y = aux.y + dy[i];
            if(b[aux1.x][aux1.y] == 0)
            {
                b[aux1.x][aux1.y] = b[aux.x][aux.y] + 1;
                u++;
                q[u] = aux1;
            }
        }
    }
    aux.x = xj;
    aux.y = yj;
    c[xj][yj] = 1;
    p = u = 1;
    q[u] = aux;
    while(p <= u)
    {
        aux = q[p];
        p++;
        for(int i = 0; i < 8; i++)
        {
            aux1.x = aux.x + dx[i];
            aux1.y = aux.y + dy[i];
            if(c[aux1.x][aux1.y] == 0)
            {
                c[aux1.x][aux1.y] = c[aux.x][aux.y] + 1;
                u++;
                q[u] = aux1;
            }
        }
    }
    int tmin = 1e6;
    int xmin , ymin;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(b[i][j] == c[i][j] && b[i][j] > 0)
               if(b[i][j] < tmin)
                {
                    tmin = b[i][j];
                    xmin = i;
                    ymin = j;
                }
    cout << tmin << " " << xmin << " " << ymin << "\n";
    cin.close();
    cout.close();
    return 0;
}