Cod sursa(job #1798483)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 5 noiembrie 2016 11:29:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <stdio.h>
#include <queue>
#include <string.h>

#define MAX_N 101

#define MAX_LINE 105

using namespace std;

struct Member
{
    bool rom;
    int y, x;
};

struct Cell
{
    bool usable;
    int romeo = -1;
    int juliet = -1;
};

FILE* fin;
FILE* fout;

int dY[] = {0, -1, 0, 1};
int dX[] = {-1, 0, 1, 0};

int n, m;

Cell oras[MAX_N][MAX_N];

queue<Member> leeQueue;

int yMin = -1;
int xMin = -1;

char line[MAX_LINE] = { NULL };

void LoadFiles()
{
    fin = fopen("rj.in", "r");
    fout = fopen("rj.out", "w");
}

void Init()
{
    LoadFiles();
}

void Read()
{
    char c;
    fgets(line, MAX_LINE, fin);
    sscanf(line, "%d %d", &n, &m);

    for(int i=0;i<n;i++)
    {
        memset(line, NULL, sizeof(char) * MAX_LINE);
        fgets(line, MAX_LINE, fin);
        for(int j=0;j<m;j++)
        {
            c = line[j];

            oras[i][j].usable = true;

            Member m;

            switch(c)
            {
            case 'X':
                oras[i][j].usable = false;
                break;
            case ' ':
                break;
            case 'R':

                m.y = i;
                m.x = j;

                m.rom = true;

                leeQueue.push(m);

                oras[i][j].romeo = 1;
                break;
            case 'J':

                m.y = i;
                m.x = j;

                m.rom = false;

                leeQueue.push(m);

                oras[i][j].juliet = 1;
                break;
            }
        }
    }
}

bool ValidPos(int y, int x)
{
    if(y >= 0 && y < n &&
       x >= 0 && x < m)
    {
        if(oras[y][x].usable)
        {
            return true;
        }
    }

    return false;
}

void Lee()
{
    Member crt;

    int y;
    int x;

    int dist;

    int newY;
    int newX;

    while(!leeQueue.empty())
    {
        crt = leeQueue.front();
        leeQueue.pop();

        y = crt.y;
        x = crt.x;

        if(crt.rom)
        {
            dist = oras[y][x].romeo;
        }
        else
        {
            dist = oras[y][x].juliet;
        }

        for(int i=0;i<4;i++)
        {
            newY = y + dY[i];
            newX = x + dX[i];

            if(ValidPos(newY, newX))
            {
                if((crt.rom && oras[newY][newX].romeo == -1) ||
                   (!crt.rom && oras[newY][newX].juliet == -1))
                {
                    if(crt.rom)
                    {
                        oras[newY][newX].romeo = dist + 1;

                        Member m;

                        m.y = newY;
                        m.x = newX;

                        m.rom = true;

                        leeQueue.push(m);
                    }
                    else
                    {
                        oras[newY][newX].juliet = dist + 1;

                        Member m;

                        m.y = newY;
                        m.x = newX;

                        m.rom = false;

                        leeQueue.push(m);
                    }
                }
            }
        }
    }
}

void Parcurg()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(oras[i][j].usable)
            {
                if(oras[i][j].romeo == oras[i][j].juliet && oras[i][j].romeo != -1)
                {
                    if(yMin == -1)
                    {
                        yMin = i;
                        xMin = j;
                    }
                    else
                    {
                        if(oras[yMin][xMin].romeo > oras[i][j].romeo)
                        {
                            yMin = i;
                            xMin = j;
                        }
                    }
                }
            }
        }
    }
}

void Solve()
{
    Lee();
    Parcurg();
}

void Write()
{
    fprintf(fout, "%d %d %d", oras[yMin][xMin].romeo-1, yMin + 1, xMin + 1);
}

void CloseFiles()
{
    fclose(fin);
    fclose(fout);
}

void Terminate()
{
    CloseFiles();
}

int main(void)
{
    Init();
    Read();
    Solve();
    Write();
    Terminate();

    return 0;
}