Cod sursa(job #2947233)

Utilizator delia.taigaTaiga Delia delia.taiga Data 25 noiembrie 2022 20:54:55
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

struct element
{
    int x;
    int y;
};

struct item
{
    int x;
    int y;
    item *next;

};

struct List
{
    item *head;
    item *tail;


    void add_first_element ( element first )
    {
        head = new item;
        head->x = first.x;
        head->y = first.y;
        head->next = NULL;
        tail = head;
    }

    void add_after_last ( element pos )
    {
        item *new_item = new item;
        new_item->x = pos.x;
        new_item->y = pos.y;
        new_item->next= NULL;
        tail->next = new_item;
        tail = new_item;
    }



};



bool isvalid( int ** a, int N, int M, element pos )
{
    if( pos.x < 0 || pos.x > N-1 || pos.y < 0 || pos.y > M-1 ) return false;
    if( a[pos.x][pos.y] == 0 ) return true;
    return false;
}


void lee( int ** a,int N, int M, element first )
{

    element directions[] = { {-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0,}, {1,-1}, {0,-1} };
    List *l = new List;
    l->add_first_element( first );
    a[l->head->x][l->head->y] = 1;

    while( l->head !=NULL )
    {
        element current;

        current.x = l->head->x;
        current.y = l->head->y;

        for( int i = 0; i < 8; i++ )
        {
            element pos;
            pos.x = current.x + directions[i].x;
            pos.y = current.y + directions[i].y;
            if( isvalid( a, N, M, pos ) )
            {
                a[pos.x][pos.y] = a[current.x][current.y] + 1;
                l->add_after_last(pos);

            }

        }

        item *removed_el = l->head;
        l->head = l->head->next;
        delete removed_el;

    }

    delete l;


}




void allocate_maze( int N, int M, int **& a )
{
    a = new int *[N];
    for( int i = 0; i < N; i++ )
        a[i] = new int [M];

}


void scan_and_make_maze( int &N, int &M, int **&romeo, int **&juliet, element &r_first, element &j_first )
{

    fin >> N >> M;
    allocate_maze( N, M, romeo );
    allocate_maze( N, M, juliet );
    fin.get();

    for( int i = 0; i < N; i++ )
    {
        char c[M+1];
        fin.getline(c,M+1);
        for( int j = 0; j < M; j++ )
        {
            romeo[i][j] = 0;
            juliet[i][j] = 0;
            if( c[j] == 'R' )
            {
                r_first.x = i;
                r_first.y = j;
            }
            else
            if( c[j] == 'J' )
            {
                j_first.x = i;
                j_first.y = j;
            }
            else
            if( c[j] == 'X' )
            {
                romeo[i][j] = -1;
                juliet[i][j] = -1;
            }

        }



    }

}


void where_meet( int N, int M, int **romeo, int **juliet, int &tmin, element &meet)
{

    for( int i = 0; i < N; i++ )
        for( int j = 0; j < M; j++ )
        {
            if( romeo[i][j] > 0 && romeo[i][j] == juliet[i][j] && romeo[i][j] < tmin )
            {
                tmin = romeo[i][j];
                meet.x = i + 1;
                meet.y = j + 1;
            }
        }
}

void print( int tmin, element meet )
{
    fout << tmin << " " << meet.x << " " << meet.y;
}



void romeo_and_juliet()
{
    int N, M;
    int ** romeo = NULL, **juliet = NULL;

    element r_first, j_first;
    scan_and_make_maze( N, M, romeo, juliet, r_first, j_first );

    lee( romeo, N, M, r_first );
    lee( juliet, N, M, j_first );

    int tmin = 10005;
    element meet;
    where_meet( N, M, romeo, juliet, tmin, meet );
    print( tmin, meet );


}

int main()
{

    romeo_and_juliet();

}