Cod sursa(job #1268404)

Utilizator smaraldaSmaranda Dinu smaralda Data 20 noiembrie 2014 22:00:23
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb

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

const int NMAX = 102;

struct POINT {
    int i, j;

    POINT (int i = 0, int j = 0) {
        this->i = i;
        this->j = j;
    }
};

queue <POINT> q;
char grid[NMAX][NMAX];
bool visr[NMAX][NMAX], visj[NMAX][NMAX];
int n, m, rom[NMAX][NMAX], jul[NMAX][NMAX];

bool inBound (int i, int j) {
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

int main() {
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    int i, j, k, tmin, soli, solj, newi, newj, di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
    POINT romeo, julieta;

    scanf("%d%d\n", &n, &m);
    for(i = 1; i <= n; ++ i, scanf("\n"))
        for(j = 1; j <= m; ++ j) {
            scanf("%c", &grid[i][j]);
            if(grid[i][j] == 'R')
                romeo = POINT(i, j);
            if(grid[i][j] == 'J')
                julieta = POINT(i ,j);
        }

    q.push(romeo);
    while(!q.empty()) {
        i = q.front().i;
        j = q.front().j;
        q.pop();

        visr[i][j] = 1;
        for(k = 0; k < 4; ++ k) {
            newi = i + di[k];
            newj = j + dj[k];
            if(inBound(newi, newj) && !visr[newi][newj] && grid[newi][newj] != 'X')
                rom[newi][newj] = rom[i][j] + 1,
                visr[newi][newj] = 1,
                q.push(POINT(newi, newj));

        }
    }

    q.push(julieta);
    while(!q.empty()) {
        i = q.front().i;
        j = q.front().j;
        q.pop();

        visj[i][j] = 1;
        for(k = 0; k < 4; ++ k) {
            newi = i + di[k];
            newj = j + dj[k];
            if(inBound(newi, newj) && !visj[newi][newj] && grid[newi][newj] != 'X')
                jul[newi][newj] = jul[i][j] + 1,
                visj[newi][newj] = 1,
                q.push(POINT(newi, newj));
        }
    }

    tmin = 2e9;
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= m; ++ j)
            if(grid[i][j] != 'X' && visr[i][j] && visj[i][j] && rom[i][j] == jul[i][j] && rom[i][j] < tmin)
                tmin = min(tmin, rom[i][j]),
                soli = i,
                solj = j;

    if(tmin == 2e9)
        printf("-1\n");
    else
        printf("%d %d %d\n", tmin, soli, solj);
    return 0;
}