Cod sursa(job #1609051)

Utilizator gabor.vlad13lil pump gabor.vlad13 Data 22 februarie 2016 16:21:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>

using namespace std;

int n, m;
int matR[105][105];
int matJ[105][105];
int dx[8] = {-1, 0, 1, -1, 1, 1, 0, -1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

struct Punct
{
    int x;
    int y;
    Punct(int a = 0, int b = 0)
    {
        x = a;
        y = b;
    }
} startR, startJ;

queue<Punct> q;

void Debug()
{
    for (int i=0; i<=n+1; i++)
    {
        for (int j=0; j<=m+1; j++)
        {
            cerr<<matR[i][j]<<" ";
        }
        cerr<<"\n";
    }
}

void LeeRomeo()
{
    q.push(Punct(startR.x, startR.y));
    matR[startR.x][startR.y] = 1;
    Punct aux;

    while(!q.empty())
    {
        aux = q.front();

        for (int i=0; i<8; i++)
        {
            if (matR[aux.x + dx[i]][aux.y + dy[i]] == 0)
            {
                matR[aux.x + dx[i]][aux.y + dy[i]] = matR[aux.x][aux.y] + 1;
                q.push(Punct(aux.x + dx[i], aux.y + dy[i]));
            }
        }

        q.pop();
    }
}

void LeeJulieta()
{
    q.push(Punct(startJ.x, startJ.y));
    matJ[startJ.x][startJ.y] = 1;
    Punct aux;

    while(!q.empty())
    {
        aux = q.front();

        for (int i=0; i<8; i++)
        {
            if (matJ[aux.x + dx[i]][aux.y + dy[i]] == 0)
            {
                matJ[aux.x + dx[i]][aux.y + dy[i]] = matJ[aux.x][aux.y] + 1;

                if (matJ[aux.x + dx[i]][aux.y + dy[i]] == matR[aux.x + dx[i]][aux.y + dy[i]])
                {
                    printf("%d %d %d", matJ[aux.x + dx[i]][aux.y + dy[i]], aux.x + dx[i], aux.y + dy[i]);
                    return;
                }

                q.push(Punct(aux.x + dx[i], aux.y + dy[i]));
            }
        }

        q.pop();
    }
}

void Solve()
{
    LeeRomeo();
    LeeJulieta();
}

void Bordare()
{
    for (int i=0; i<=n+1; i++)
    {
        for (int j=0; j<=m+1; j++)
        {
            if (i==0 || i==n+1 || j==0 || j==m+1)
                matR[i][j] = -1;
        }
    }
}

void Read()
{
    char aux;
    scanf("%d %d\n", &n, &m);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            matR[i][j] = 0;
            scanf("%c", &aux);
            if (aux == 'R')
            {
                startR.x = i;
                startR.y = j;
            }
            else if (aux == 'J')
            {
                startJ.x = i;
                startJ.y = j;
            }
            else if (aux == 'X')
                matR[i][j] = -1;
        }
        scanf("\n");
    }

    Bordare();
    memcpy(matJ, matR, sizeof(matR));
}

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    Read();
    Solve();
   // Debug();
    return 0;
}