Cod sursa(job #1498765)

Utilizator tudorcomanTudor Coman tudorcoman Data 9 octombrie 2015 07:25:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <queue>
using namespace std;

class Casuta {
public:
    int x, y;
    Casuta() { }
    Casuta(int x, int y) {
        this->x = x, this->y = y;
    }

    Casuta operator + (const Casuta& other) {
        return Casuta(this->x + other.x, this->y + other.y);
    }
} dir[] = {
    Casuta(-1, 0),
    Casuta(+1, 0),
    Casuta(0, -1),
    Casuta(0, +1),
    Casuta(+1, +1),
    Casuta(-1, -1),
    Casuta(-1, +1),
    Casuta(+1, -1)
}, Rs, Js;

queue<Casuta> C;
int R[103][103], J[103][103], N, M;
bool viz[103][103];
void BFS_1() {
    for(register int i = 0; i < 103; ++ i)
        for(register int j = 0; j < 103; ++ j)
            if(R[i][j] != -1)
                R[i][j] = -2;

    viz[Rs.x][Rs.y] = 1;
    R[Rs.x][Rs.y] = 0;
    C.push(Rs);

    while(!C.empty()) {
        Casuta c = C.front();
        C.pop();
        for(register int k = 0; k < 8; ++ k) {
            Casuta v = c + dir[k];
            if(1 <= v.x and v.x <= N and 1 <= v.y and v.y <= M)
                if(!viz[v.x][v.y] and R[v.x][v.y] != -1) {
                    viz[v.x][v.y] = 1;
                    C.push(v);
                    R[v.x][v.y] = 1 + R[c.x][c.y];
                }
        }
    }
}
void BFS_2() {

    memset(viz, 0, sizeof(viz));
    while(!C.empty()) C.pop();
    for(register int i = 0; i < 103; ++ i)
        for(register int j = 0; j < 103; ++ j)
            if(J[i][j] != -1)
                J[i][j] = -2;

    J[Js.x][Js.y] = 0;
    C.push(Js);
    viz[Js.x][Js.y] = 1;

    while(!C.empty()) {
        Casuta c = C.front();
        C.pop();
        for(register int k = 0; k < 8; ++ k) {
            Casuta v = c + dir[k];
            if(1 <= v.x and v.x <= N and 1 <= v.y and v.y <= M)
                if(!viz[v.x][v.y] and J[v.x][v.y] != -1) {
                    viz[v.x][v.y] = 1;
                    C.push(v);
                    J[v.x][v.y] = 1 + J[c.x][c.y];
                }
        }
    }
}
int main(void) {
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    scanf("%d %d\n", &N, &M);
    for(register int i = 1; i <= N; ++ i) {
        string str;
        getline(cin, str);
        string :: iterator it = str.begin();

        for(register int j = 1; j <= M and it != str.end(); ++ j, ++ it) {
            switch(*it) {
                case 'R': Rs = Casuta(i, j); break;
                case 'J': Js = Casuta(i, j); break;
                case 'X': R[i][j] = J[i][j] = -1; break;
            }
        }
    }



    BFS_1();
    BFS_2();

    int minim = 1 << 30;
    Casuta Min;

    for(register int i = 1; i <= N; ++ i)
        for(register int j = 1; j <= M; ++ j)
            if(R[i][j] == J[i][j] and R[i][j] != -1 and R[i][j] != -2 and R[i][j] < minim) {
                minim = R[i][j];
                Min = Casuta(i, j);
                fprintf(stderr, "%d %d\n", i, j);
            }

    printf("%d %d %d\n", ++ minim, Min.x, Min.y);
    return 0;
}