Cod sursa(job #2666033)

Utilizator miramaria27Stroie Mira miramaria27 Data 31 octombrie 2020 18:22:49
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <queue>
#include <string>
#include <fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
///pentru a schimba pozitia pionului, relativ la pozitia sa initiala
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int matrixr[101][101];
int matrixj[101][101];
int n,m;

struct cell
{
    int x,y;
    cell(int x = 0, int y = 0):x(x),y(y) {}
};
queue<cell> c1;
queue<cell> c2;

int in(int x, int y)
{
    if(x >= 0 && x < n && y >=0 && y < m)
        return 1;
    return 0;
}
void leer()
{
    while(!c1.empty())
    {

        cell parent =  c1.front();
        for(int i = 0; i < 8; i++)
        {
            int x = parent.x + dx[i];
            int y = parent.y + dy[i];

            if(in(x,y) == 1 && matrixr[x][y] == 0)
            {

                matrixr[x][y] = matrixr[parent.x][parent.y] + 1;
                c1.push(cell(x,y));
            }
        }
        c1.pop();

    }
}
void leej()
{
    while(!c2.empty())
    {

        cell parent =  c2.front();
        for(int i = 0; i < 8; i++)
        {
            int x = parent.x + dx[i];
            int y = parent.y + dy[i];

            if(in(x,y) == 1 && matrixj[x][y] == 0)
            {

                matrixj[x][y] = matrixj[parent.x][parent.y] + 1;
                c2.push(cell(x,y));
            }
        }
        c2.pop();

    }
}
int main()
{

    cell start;
    cell finish;

    ///citim datele
    fin>>n>>m;
    fin.get();
    for(int i=0; i<n; i++)
    {
        string str;
        getline(fin,str);
        for(int j = 0; j < str.length(); j ++)
        {
            if(str[j] == 'R')
            {
                start.x = i;
                start.y = j;
            }
            else if(str[j] == 'J')
            {
                finish.x = i;
                finish.y = j;
            }
            else if(str[j] == 'X')
            {
                matrixr[i][j] = -1;
                matrixj[i][j] = -1;
            }

        }
    }


    ///housekeeping stuff
    c1.push(start);
    c2.push(finish);
    matrixr[start.x][start.y] = 1;
    matrixj[finish.x][finish.y] = 1;
    ///apelam 2 lee-uri: unul pentru julieta si unul pentru romeo
    leer();
    leej();
    ///cautam drumul minim
    int minim = 100000,x,y;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
    {

        if (matrixr[i][j] == matrixj[i][j] && matrixj[i][j] < minim && matrixr[i][j] > 0)
        {
            minim = matrixj[i][j];
            x = i;
            y = j;
        }


    }
    fout<<minim  <<" "<< x + 1 << " " << y + 1;
    return 0;
}