Cod sursa(job #1618494)

Utilizator Tomi98Osvath Tamas Tomi98 Data 27 februarie 2016 20:51:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <deque>
#include <string>
#define L 105

using namespace std;

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

int e[L][L], n, m, nrPasi, e2[L][L];
bool d[L][L], seen1[L][L], seen2[L][L], pozGasit[L][L];

int dl[4] = {-1, 0, 0, 1};
int dc[4] = {0, -1, 1, 0};

string s;

struct P{
    int l, c;
}a, b, p, v;

deque <P > C;

bool check(int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m && seen1[i][j] == 0 && d[i][j] == 0) return 1;
    return 0;
}

bool check2(int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m && seen2[i][j] == 0 && d[i][j] == 0) return 1;
    return 0;
}
int main()
{
    fin >> n >> m;

    fin.get();

    for (int i = 1; i <= n; i++){
        getline(fin, s);
        for (int j = 0; j < s.size(); j++){
            if (s[j] == 'R'){
                d[i][j + 1] = 0;
                a.l = i; a.c = j + 1;
            }
            if (s[j] == 'X')
                d[i][j + 1] = 1;
            if (s[j] == ' ')
                d[i][j + 1] = 0;
            if (s[j] == 'J'){
                d[i][j + 1] = 0;
                b.l = i; b.c = j + 1;
            }
        }
    }

    /*for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
            fout << d[i][j] << " ";
        fout << endl;
    }*/

    C.push_back(a);
    while (!C.empty()){
        p = C.front();
        C.pop_front();
        for (int i = 0; i <= 3; i++){
            v.l = p.l + dl[i];
            v.c = p.c + dc[i];
            if (check(v.l, v.c)){
                seen1[v.l][v.c] = 1;
                e[v.l][v.c] = e[p.l][p.c] + 1;
                C.push_back(v);
            }
        }
        if (seen1[b.l][b.c] == 1) break;
    }

    //fout << e[b.l][b.c] << endl;

    if (e[b.l][b.c] % 2 == 0) nrPasi = e[b.l][b.c] / 2;
        else nrPasi = e[b.l][b.c] / 2 + 1;

    C.clear();
    C.push_back(b);
    e2[b.l][b.c] = 0;
    while (!C.empty()){
        p = C.front();
        C.pop_front();
        for (int i = 0; i <= 3; i++){
            v.l = p.l + dl[i];
            v.c = p.c + dc[i];
            if (check2(v.l, v.c)){
                seen2[v.l][v.c] = 1;
                e2[v.l][v.c] = e2[p.l][p.c] + 1;
                C.push_back(v);
                if (e2[v.l][v.c] == nrPasi && seen1[v.l][v.c] == 1)
                    pozGasit[v.l][v.c] = 1;
            }
        }
        if (seen2[a.l][a.c] == 1) break;
    }

    fout << nrPasi << " ";

    bool ok = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
            if (pozGasit[i][j] == 1){
                fout << i << " " << j;
                ok = 1;
                break;
            }
        if (ok == 1) break;
    }

    return 0;
}