Cod sursa(job #1313643)

Utilizator smaraldaSmaranda Dinu smaralda Data 10 ianuarie 2015 22:14:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 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, -1, 0, 1, 1, 1, 0, -1}, dj[] = {0, 1, 1, 1, 0, -1, -1, -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 < 8; ++ 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 < 8; ++ 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;
}