Cod sursa(job #1622685)

Utilizator Tomi98Osvath Tamas Tomi98 Data 1 martie 2016 13:32:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 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, e2[L][L], lin, col;
bool d[L][L], seen1[L][L], seen2[L][L];

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

string s;

int mx = 10010;

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;
            }
        }
    }

    e[a.l][a.c] = seen1[a.l][a.c] = 1;
    e2[b.l][b.c] = seen2[b.l][b.c] = 1;

    C.push_back(a);
    while (!C.empty()){
        p = C.front();
        C.pop_front();
        for (int i = 0; i <= 7; 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;
    }

    C.clear();
    C.push_back(b);
    while (!C.empty()){
        p = C.front();
        C.pop_front();
        for (int i = 0; i <= 7; 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 (seen2[a.l][a.c] == 1) break;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (e[i][j] == e2[i][j] && d[i][j] == 0 && e[i][j] < mx && e[i][j] != 0){
                mx = e[i][j];
                lin = i;
                col = j;
            }

    fout << mx << " " << lin << " " << col;

    return 0;
}