Cod sursa(job #686878)

Utilizator hamfauHamfau Marian hamfau Data 21 februarie 2012 22:08:09
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>

#define MAX 105
#define INF 20000

using namespace std;

typedef struct coada
{
    short val;
    char x, y;
};



vector<coada> romeo, julieta;
int n,m;
char matrice[MAX][MAX];
short r[MAX][MAX], j[MAX][MAX];
char depl_x[] = {-1, -1, 0, 1, 1, 1, 0, -1};
char depl_y[] = {0, 1, 1, 1, 0, -1, -1, -1};
int bestX, bestY, best = INF;

void citire()
{
    ifstream in("rj.in");
    in>>n>>m;
    in.get();
    int i, h;
    coada a;
    for(i = 0; i < n; i++)
    {
        in.getline(matrice[i], MAX);
        matrice[i][strlen(matrice[i])] = '\n';
        for(h = 0; h < m; h++)
        {
            if(matrice[i][h] == 'R')
            {
                r[i][h] = 1;
                a.val = 1;
                a.x = i;
                a.y = h;
                romeo.push_back(a);
            }
            else if(matrice[i][h] == 'J')
            {
                j[i][h] = 1;
                a.val = 1;
                a.x = i;
                a.y = h;
                julieta.push_back(a);
            }
        }
    }
    in.close();
}

void leeRomeo()
{
    int a = 0;
    int i;
    coada nou;
    while(a < romeo.size())
    {
        for(i = 0; i < 8; i++)
        {
            if(romeo[a].x + depl_x[i] < n && romeo[a].x + depl_x[i] >= 0 &&
               romeo[a].y + depl_y[i] < m && romeo[a].y + depl_y[i] >= 0 &&
               matrice[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] != 'X' &&
               r[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] == INF)
               {
                   nou.x = romeo[a].x + depl_x[i];
                   nou.y = romeo[a].y + depl_y[i];
                   nou.val = romeo[a].val + 1;
                   romeo.push_back(nou);
                   r[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] = nou.val;
               }
        }
        a++;
    }
}

void leeJulieta()
{
    int a = 0;
    int i;
    coada nou;
    while(a < julieta.size())
    {
        for(i = 0; i < 8; i++)
        {
            if(julieta[a].x + depl_x[i] < n && julieta[a].x + depl_x[i] >= 0 &&
               julieta[a].y + depl_y[i] < m && julieta[a].y + depl_y[i] >= 0 &&
               j[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] == INF &&
               matrice[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] != 'X')
               {
                   nou.x = julieta[a].x + depl_x[i];
                   nou.y = julieta[a].y + depl_y[i];
                   nou.val = julieta[a].val + 1;
                   julieta.push_back(nou);
                   j[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] = nou.val;
               }
        }
        a++;
    }
}

void findSolution()
{
    int i, h;
    for(i = 0; i < n; i++)
    {
        for(h = 0; h < m; h++)
        {
            if(r[i][h] == j[i][h] && r[i][h] < best)
            {
                best = r[i][h];
                bestX = i;
                bestY = h;
            }
        }
    }
}

void afisare()
{
    ofstream out("rj.out");
    out<<best<<" "<<bestX + 1<<" "<<bestY + 1;
}

void init()
{
    int i, h;
    for(i = 0; i < n; i++)
    {
        for(h = 0; h < m; h++)
        {
            r[i][h] = j[i][h] = INF;
        }
    }
    r[romeo[0].x][romeo[0].y] = 1;
    j[julieta[0].x][julieta[0].y] = 1;
}

int main()
{
    citire();
    init();
    leeRomeo();
    leeJulieta();
    findSolution();
    afisare();
    return 0;
}