Cod sursa(job #561035)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 18 martie 2011 20:20:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <queue>

using namespace std;

const int N = 105;

int n, m, xR, yR, xJ, yJ, R[N][N], J[N][N];

char a[N][N];

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

queue<pair<int, int> > Q;

void read() {
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            scanf("%c",&a[i][j]);
            if (a[i][j] == 'R')
                xR = i, yR = j;
            else if (a[i][j] == 'J')
                xJ = i, yJ = j;
            else if (a[i][j] != 'X')
                a[i][j] = ' ';
        }
        scanf("\n");
    }
}

void bordeaza() {
    for (int i = 0; i <= n + 1; ++ i)
        a[i][0] = a[i][m + 1] = 'X';
    for (int j = 0; j <= m + 1; ++ j)
        a[0][j] = a[n + 1][j] = 'X';
}

void lee(int xi, int yi, int m[N][N]) {
    pair<int, int> nod, nodc;
    Q.push(make_pair(xi, yi));
    m[xi][yi] = 1;
    while (! Q.empty()) {
        nod = Q.front();
        Q.pop();
        for (int i = 0; i <= 8; ++ i) {
            nodc.first = nod.first + dl[i];
            nodc.second = nod.second + dc[i];
            if(m[nodc.first][nodc.second] == 0 && a[nodc.first][nodc.second] == ' ') {
                m[nodc.first][nodc.second] = m[nod.first][nod.second] + 1;
                Q.push(nodc);
            }
        }
    }
}

void solve() {
    int rez = 2000000000, px = 0, py = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (R[i][j] == J[i][j] && R[i][j] != 0 && rez > R[i][j]) {
                rez = R[i][j];
                px = i;
                py = j;
            }
    printf("%d %d %d\n", rez, px, py);
}

int main() {
    read();
    bordeaza();
    lee(xR,yR,R);
    lee(xJ,yJ,J);
    solve();
    return 0;
}