Cod sursa(job #1781663)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 17 octombrie 2016 10:29:02
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

const int DMAX = 100; //Dimensiunea maxima a labirintului
struct pozitie
{
    int x, y;
};

int M, N, D, X, Y, L[DMAX + 2][DMAX + 2],TIMP; //Labirintul
char linie[DMAX + 2];
pozitie C1[DMAX * DMAX + 1], C2[DMAX * DMAX + 1]; //Coada
int p1, u1, p2, u2;

pozitie ps; //Pozitia initiala a soricelului
pozitie pc; //Pozitia cascavalului

int d[4][2] = {{0, -1}, { -1, 0}, {0, 1}, {1, 0}}; //Modalitati de deplasare in labirint

void bordare()
{
    int i;
    for (i = 0; i <= M + 1; i++)
        L[i][0] = L[i][N + 1] = -1;
    for (i = 0; i <= N + 1; i++)
        L[0][i] = L[M + 1][i] = -1;
}

void Lee()
{
    pozitie vec1, crt1, vec2, crt2;
    p1 = u1 = 1;
    p2 = u2 = 1;
    C1[1] = ps;
    C2[1] = pc;
    TIMP=0;
    while (p1 <= u1 && p2 <= u2)
    {
        crt1 = C1[p1++];//Se extrage un element din coada
        crt2 = C2[p2++];
        for (int k = 0; k < 4; k++) //Se parcurg vecinii pozitiei curente
        {
            vec1.x = crt1.x + d[k][0]; //Se obtin coordonatele vecinului
            vec1.y = crt1.y + d[k][1];
            vec2.x = crt2.x + d[k][0]; //Se obtin coordonatele vecinului
            vec2.y = crt2.y + d[k][1];
            if (L[vec1.x][vec1.y] == 0) //Vecinul este un culoar nevizitat
            {
                L[vec1.x][vec1.y] = L[crt1.x][crt1.y]; //Creste distanta minima
                C1[++u1] = vec1; //Adaugare vecin in coada
            }
            else if (L[vec1.x][vec1.y] == 3)
            {
                D = L[vec1.x][vec1.y];
                X = vec1.x;
                Y = vec1.y;
                p1 = u1 + 1;
                break;
            }
            if (L[vec2.x][vec2.y] == 0) //Vecinul este un culoar nevizitat
            {
                L[vec2.x][vec2.y] = L[crt2.x][crt2.y]; //Creste distanta minima
                C2[++u2] = vec2; //Adaugare vecin in coada
            }
            else if (L[vec2.x][vec2.y] == 2)
            {
                D = L[vec2.x][vec2.y];
                X = vec2.x;
                Y = vec2.y;
                p2 = u2 + 1;
                break;
            }

        }
        TIMP++;
       // afisare();
    }
}


int main()
{
    ifstream f ("rj.in");
    ofstream g ("rj.out");
    f >> M >> N;
    f.getline(linie, 100);
    for (int i = 1; i <= M; i++)
    {
        f.getline (linie, 100);
        for (int j = 0; j < N; j++)
            if (linie[j] == 'R')
                ps.x = i, ps.y = j + 1, L[ps.x][ps.y]=2;
            else if (linie[j] == 'J')
                pc.x = i, pc.y = j + 1, L[pc.x][pc.y]=3;
            else if (linie[j] == 'X')
                L[i][j + 1] = -1;
    }

    bordare();
    Lee();

    g << TIMP - 1 <<' '<< X <<' '<< Y;
    return 0;
}