Cod sursa(job #2943883)

Utilizator delia.taigaTaiga Delia delia.taiga Data 21 noiembrie 2022 19:07:25
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.83 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;
        removed_el = NULL;

    }

    delete l;

}



void scan( int &N, int &M, char **& init )
{
    fin >> N >> M;
    char c;
    fin.get(c);
    init = new char *[N];
    for( int  i = 0; i < N; i++ )
        init[i] =  new char [M];
    for( int i = 0 ; i < N; i++ )
    {

        for( int j = 0; j < M ; j++ )
            fin.get(init[i][j]);
        fin.get(c);
    }

}

void make_maze( int N, int M, int **&a, element &a_first, char c , char **init )
{
     a = new int *[N];
    for( int i = 0; i < N; i++ )
        a[i] = new int[M];
    for( int i = 0; i < N; i++ )
        for( int j = 0; j < M; j++ )
        {
            a[i][j] = 0;
            if( init[i][j] == 'X') a[i][j] =-1;
            if( init[i][j] == 'R' && c == 'R')
            {

                    a_first.x = i;
                    a_first.y = j;


            }
            if( init[i][j] == 'J' && c == 'J' )
            {

                    a_first.x = i;
                    a_first.y = j;


            }

        }
}




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;
    char ** init = NULL;
    int ** romeo = NULL, **juliet = NULL;

    scan( N, M, init );
    element r_first, j_first;
    make_maze( N, M, romeo , r_first ,'R', init );
    make_maze( N, M, juliet, j_first, 'J', init );

    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();

}