Cod sursa(job #860640)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 20 ianuarie 2013 15:49:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.36 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
struct cuplu {
    int a, b;
};
int i, j, m, n, mini = 120, f, g;
queue<cuplu> coada;
string a; cuplu xy, v[100][100];

void r(int x, int y) {
    coada.pop();
    if((v[x][y + 1].a == 0) && (y < m - 1)) {
        xy.a = x;
        xy.b = y + 1;
        v[x][y + 1].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x + 1][y + 1].a == 0) && (y < m - 1) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y + 1;
        v[x + 1][y + 1].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x + 1][y].a == 0) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y;
        v[x + 1][y].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x + 1][y - 1].a == 0) && (y > 0) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y - 1;
        v[x + 1][y - 1].a = v[x][y].a + 1;
        coada.push(xy);
}
    if((v[x][y - 1].a == 0) && (y > 0)) {
        xy.a = x;
        xy.b = y - 1;
        v[x][y - 1].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x - 1][y - 1].a == 0) && (x > 0) && (y > 0)) {
        xy.a = x - 1;
        xy.b = y - 1;
        v[x - 1][y - 1].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x - 1][y].a == 0) && (x > 0)) {
        xy.a = x - 1;
        xy.b = y;
        v[x - 1][y].a = v[x][y].a + 1;
        coada.push(xy);
    }
    if((v[x - 1][y + 1].a == 0) && (y < m - 1) && (x > 0)) {
        xy.a = x - 1;
        xy.b = y + 1;
        v[x - 1][y + 1].a = v[x][y].a + 1;
        coada.push(xy);
    }
}

void ju(int x, int y) {
    coada.pop();
    if((v[x][y + 1].b == 0) && (y < m - 1)) {
        xy.a = x;
        xy.b = y + 1;
        v[x][y + 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x + 1][y + 1].b == 0) && (y < m - 1) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y + 1;
        v[x + 1][y + 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x + 1][y].b == 0) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y;
        v[x + 1][y].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x + 1][y - 1].b == 0) && (y > 0) && (x < n - 1)) {
        xy.a = x + 1;
        xy.b = y - 1;
        v[x + 1][y - 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x][y - 1].b == 0) && (y > 0)) {
        xy.a = x;
        xy.b = y - 1;
        v[x][y - 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x - 1][y - 1].b == 0) && (x > 0) && (y > 0)) {
        xy.a = x - 1;
        xy.b = y - 1;
        v[x - 1][y - 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x - 1][y].b == 0) && (x > 0)) {
        xy.a = x - 1;
        xy.b = y;
        v[x - 1][y].b = v[x][y].b + 1;
        coada.push(xy);
    }
    if((v[x - 1][y + 1].b == 0) && (y < m - 1) && (x > 0)) {
        xy.a = x - 1;
        xy.b = y + 1;
        v[x - 1][y + 1].b = v[x][y].b + 1;
        coada.push(xy);
    }
}

int main() {
    fin >> n >> m;
    getline(fin, a);
    for(i = 0; i < n; i++) {
        getline(fin, a);
        for(j = 0; j < m; j++) {
            if(a[j] == ' ') {
                v[i][j].a = 0;
                v[i][j].b = 0;
            }
            if(a[j] == 'X') {
                v[i][j].a = -1;
                v[i][j].b = -1;
            }
            if(a[j] == 'R') {
                v[i][j].a = 1;
                xy.a = i;
                xy.b = j;
                coada.push(xy);
            }
            if(a[j] == 'J') {
                v[i][j].b = 1;
                f = i;
                g = j;
            }
        }
    }
    xy = coada.front();
    while(!coada.empty()) {
        xy = coada.front();
        r(xy.a, xy.b);
    }
    xy.a = f;
    xy.b = g;
    coada.push(xy);
    while(!coada.empty()) {
        xy = coada.front();
        ju(xy.a, xy.b);
    }
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if((v[j][i].a == v[j][i].b) && (v[j][i].a != -1) && (v[j][i].a != 0)) {
                if(v[j][i].a < mini) {
                    mini = v[j][i].a;
                    f = j;
                    g = i;
                }
            }
        }
    }
    fout << mini << ' ' << f + 1 << ' ' << g + 1;
    fin.close();
    fout.close();
    return 0;
}