Cod sursa(job #1894927)

Utilizator osiaccrCristian Osiac osiaccr Data 27 februarie 2017 17:49:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <string>
#include <deque>
#define DEF 101

using namespace std;

ifstream fin ("rj.in");
ofstream fout ("rj.out");

struct coada {
    unsigned short x;
    unsigned short y;
    unsigned short p;
};

unsigned short R_i, R_j, J_i, J_j, n, m, A[DEF][DEF], F[DEF][DEF], sol = DEF*DEF, sol_i, sol_j;

deque <coada> c;

short di[] = {-1, -1, -1, 0, 1, 1, 1, 0},
      dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};

coada cons (unsigned short x, unsigned y, unsigned p) {
    coada temp;
    temp.x = x;
    temp.y = y;
    temp.p = p;
    return temp;
}

int main () {
    fin >> n >> m;
    char read[DEF];
    for (int i = 1; i <= n; i++) {
        fin.get ();
        fin.get (read + 1, DEF);
        for (int j = 1; j <= m; j++) {
            if (read[j] == 'X')
                A[i][j] = DEF*DEF;
            if (read[j] == 'R') {
                R_i = i;
                R_j = j;
            }
            if (read[j] == 'J') {
                J_i = i;
                J_j = j;
            }
        }
    }

    c.push_back (cons (R_i, R_j, 0));
    F[R_i][R_j] = DEF*DEF + 1;
    while (!c.empty()) {
        short i = c.front ().x;
        short j = c.front ().y;
        short p = c.front ().p;
        for (int d = 0; d < 8; d++) {
            short new_i = i + di[d];
            short new_j = j + dj[d];
            if (F[new_i][new_j] == 0 && new_i >= 1 && new_i <= n && new_j >= 1 && new_j <= m && A[new_i][new_j] != DEF*DEF) {
                F[new_i][new_j] = p + 1;
                c.push_back (cons (new_i, new_j, p + 1));
            }
        }
        c.pop_front ();
    }

    c.erase (c.begin (), c.end ());

    c.push_back (cons (J_i, J_j, 0));
    A[J_i][J_j] = DEF*DEF + 1;
    while (!c.empty ()) {
        short i = c.front ().x;
        short j = c.front ().y;
        short p = c.front ().p;
        for (int d = 0; d < 8; d++) {
            short new_i = i + di[d];
            short new_j = j + dj[d];
            if (A[new_i][new_j] == 0 && new_i >= 1 && new_i <= n && new_j >= 1 && new_j <= m) {
                A[new_i][new_j] = p + 1;
                c.push_back (cons (new_i, new_j, p + 1));
                if (A[new_i][new_j] == F[new_i][new_j] && A[new_i][new_j] == sol && new_j < sol_j) {
                    sol_i = i;
                    sol_j = j;
                    continue;
                }
                if (A[new_i][new_j] == F[new_i][new_j] && A[new_i][new_j] < sol) {
                    sol = A[new_i][new_j];
                    sol_i = new_i;
                    sol_j = new_j;
                }
            }
        }
        c.pop_front ();
    }

    fout << sol + 1 << " " << sol_i << " " << sol_j << "\n";

    return 0;
}