Cod sursa(job #1789217)

Utilizator eddie.deaconuDeaconu Stefan-Eduard eddie.deaconu Data 26 octombrie 2016 19:44:33
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>

using namespace std;

const int DMAX = 100;
struct pozitie
{
    unsigned char x, y;
};

int M, N;
short R[DMAX + 2][DMAX + 2], J[DMAX + 2][DMAX + 2];

pozitie C[DMAX * DMAX + 1], jl, rm;
int p, u = 0;

int d[8][2] = {{ -1, -1}, { -1, 0}, { -1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}; //Modalitati de deplasare in labirint

void bordare()
{
    int i;
    for(i = 0; i <= M + 1; i++)
        R[i][0] = R[i][N + 1] = J[i][0] = J[i][N + 1] = -1;
    for(i = 0; i <= N + 1; i++)
        R[0][i] = R[M + 1][i] = J[0][i] = J[M + 1][i] = -1;
}

void Lee(short L[][DMAX + 2], pozitie start, pozitie oprit)
{
    pozitie vec, crt;
    p = u = 1;
    C[1] = start;
    while(p <= u && L[oprit.x][oprit.y] == 0)
    {
        crt = C[p++];
        for(int k = 0; k < 8; k++)
        {
            vec.x = crt.x + d[k][0];
            vec.y = crt.y + d[k][1];
            if(L[vec.x][vec.y] == 0)
            {
                L[vec.x][vec.y] = L[crt.x][crt.y] + 1;
                C[++u] = vec;
            }
        }
    }
}

int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");
    char c[DMAX + 1];
    f >> M >> N;
    f.get();
    for(int i = 1; i <= M; i++)
    {
        f.getline(c, DMAX + 1);
        for(int j = 0; j < N; j++)
        {
            switch(c[j])
            {
            case 'X':
                R[i][j + 1] = J[i][j + 1] = -1;
                break;
            case ' ':
                R[i][j + 1] = J[i][j + 1] = 0;
                break;
            case 'R':
                R[i][j + 1] = 1;
                rm.x = i;
                rm.y = j + 1;
                break;
            case 'J':
                J[i][j + 1] = 1;
                jl.x = i;
                jl.y = j + 1;
            }
        }
    }
    bordare();
    Lee(R, rm, jl);
    Lee(J, jl, rm);
    int solx = 0, soly = 0, vsol = DMAX * DMAX + 1;
    for(int i = 1; i <= M; i++)
    {
        for(int j = 1; j <= N ; j++)
            if(R[i][j] > 0 && R[i][j] == J[i][j])
            {
                if(R[i][j] < vsol)
                {
                    solx = i;
                    soly = j;
                    vsol = R[i][j];
                }
            }
    }
    g << vsol << ' ' << solx << ' ' << soly;
    f.close();
    g.close();
    return 0;
}