Cod sursa(job #2113879)

Utilizator CelestialHunterBalea Andrei - Petru CelestialHunter Data 25 ianuarie 2018 10:43:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

struct node
{
    int x,y,val,distR, distJ;
};

const int mutX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int mutY[] = {0, 1, 1, 1, 0, -1, -1, -1};
//N, N-E, E, S-E, S, S-W, W, N-W

/*
    Legenda:
    -1 = bordura
    1 = drum deschis
    0 = perete
    2 = start romeo
    3 = start julieta
*/

queue<node> coada;
node Julieta, intersectie;
int main()
{
    ifstream f ("rj.in");
    ofstream g ("rj.out");

    int n,m;
    node mat[101][101];
    f>>n>>m;
    f.get();

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            mat[i][j].x=i;
            mat[i][j].y=j;
            char x;
            bool citit = false;
            while(!citit)
            {
                f.get(x);
                if(x=='X') {mat[i][j].val = 0; citit=true;}
                else if (x==' ') { mat[i][j].val = 1; mat[i][j].distR = -1; mat[i][j].distJ = -1; citit=true;}
                else if (x=='R') { mat[i][j].val = 2; mat[i][j].distR = 0; coada.push(mat[i][j]); citit=true; }
                else if (x=='J') { mat[i][j].val = 3; mat[i][j].distJ = 0; Julieta = mat[i][j]; citit=true; }
            }

        }
    }

    //bordare matrice
    node bordura;
    bordura.val = -1;
    bordura.x=-1;
    bordura.y=-1;
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m;j++)
        {
            mat[i][0] = bordura;
            mat[i][m+1] = bordura;
            mat[0][j] = bordura;
            mat[n+1][j] = bordura;
        }

    //lee de la Romeo pe toata matricea
    while(!coada.empty())
    {
        node currentPos = coada.front();
        coada.pop();
        for(int i=0;i<=7;i++)
        {
            node nextPos = currentPos;
            nextPos.x+=mutX[i];
            nextPos.y+=mutY[i];
            nextPos.distR++;
            if(mat[nextPos.x][nextPos.y].val==1 && mat[nextPos.x][nextPos.y].distR==-1)
            {
                mat[nextPos.x][nextPos.y].distR = nextPos.distR;
                coada.push(nextPos);
            }
        }
    }

    //lee Julieta
    coada.push(Julieta);
    bool found = false;
    while(!coada.empty() & !found)
    {
        node currentPos = coada.front();
        coada.pop();
        for(int i=0;i<=7;i++)
        {
            node nextPos = currentPos;
            nextPos.x+=mutX[i];
            nextPos.y+=mutY[i];
            nextPos.distJ++;
            if(mat[nextPos.x][nextPos.y].val==1 && mat[nextPos.x][nextPos.y].distJ == -1)
            {
                mat[nextPos.x][nextPos.y].distJ = nextPos.distJ;
                coada.push(nextPos);
                if(mat[nextPos.x][nextPos.y].distJ == mat[nextPos.x][nextPos.y].distR)
                {
                    found = true;
                    intersectie = mat[nextPos.x][nextPos.y];
                }
            }
        }
    }

      g<<intersectie.distR<<" "<<intersectie.x<<" "<<intersectie.y<<'\n';

    f.close();
    g.close();
    return 0;
}