Cod sursa(job #1569868)

Utilizator TimoteiCopaciu Timotei Timotei Data 15 ianuarie 2016 23:34:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <iostream>
using namespace std;
int N, M, Prim, Ultim, mx = 10005;
string s;
struct pozitie{
    short lin, col;
} C[10005], Romeo, Julieta, poz;
struct martrice{
    short R, J;
}dp[105][105];
short dl[8] = {0, 1, 1, 1, 0, -1, -1, -1};
short dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};

ifstream f("rj.in");
ofstream g("rj.out");
void afisare()
{
     for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++)g << dp[i][j].R << " ";
        g << "\n";
     }
}
int main()
{
    f >> N >> M;
    for(int i = 0; i <= N + 1; i++)
        dp[i][0].R = dp[i][0].J = dp[i][M + 1].R =dp[i][M + 1].J = -1;
    for(int i = 0; i <= M + 1; i++)
        dp[0][i].R = dp[0][i].J = dp[N + 1][i].R = dp[N + 1][i].J = -1;

     getline(f, s);
    for(int i = 1; i <= N; i++){
        getline(f, s);
        for(int j = 0; j < s.size(); j++){
                if(s[j] == 'X') dp[i][j + 1].R = dp[i][j + 1].J = -1;
            if(s[j] == 'R') {
                dp[i][j + 1].R = 1;
                Romeo.lin = i;
                Romeo.col = j + 1;
            }
             if(s[j] == 'J') {
                dp[i][j + 1].J = 1;
                Julieta.lin = i;
                Julieta.col = j + 1;
            }
        }
    }

    C[0] = Romeo;

    while(Prim <= Ultim)
    {
        for(int i = 0; i < 8; i++){
            if(dp[C[Prim].lin + dl[i]][C[Prim].col + dc[i]].R == 0){
            dp[C[Prim].lin + dl[i]][C[Prim].col + dc[i]].R = dp[C[Prim].lin][C[Prim].col].R + 1;
            Ultim++;
            C[Ultim].lin = C[Prim].lin + dl[i];
            C[Ultim].col = C[Prim].col + dc[i];
            }

        }
        Prim++;
    }


    Prim = Ultim = 0;
    C[0] = Julieta;
    while(Prim <= Ultim)
    {
        for(int i = 0; i < 8; i++){
            if(dp[C[Prim].lin + dl[i]][C[Prim].col + dc[i]].J == 0){
            dp[C[Prim].lin + dl[i]][C[Prim].col + dc[i]].J = dp[C[Prim].lin][C[Prim].col].J + 1;
            Ultim++;
            C[Ultim].lin = C[Prim].lin + dl[i];
            C[Ultim].col = C[Prim].col + dc[i];
            }

        }
          Prim++;
    }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        if(dp[i][j].R == dp[i][j].J && dp[i][j].R != -1 && dp[i][j].R != 0 && dp[i][j].R < mx) {
        mx= dp[i][j].R;
        poz.lin = i;
        poz.col = j;
        }


    g << mx << " " << poz.lin << " " << poz.col;

    return 0;
}