Cod sursa(job #1142394)

Utilizator DanielSanduSandu Daniel DanielSandu Data 13 martie 2014 20:06:11
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <queue>
#include <string>

std::ifstream in("rj.in");
std::ofstream out("rj.out");

int rMat[101][101], jMat[101][101], i, j, tmin, rx, ry, jx, jy, n, m;
std::pair<int, int> result;

void BF(int (*mat)[101], int sx, int sy) {
    int qx, qy;
    std::queue<std::pair<int, int>> que;
    que.push({sx, sy});
    mat[sy][sx] = 1;
    while (!que.empty()) {
        for (int x = -1; x <= 1; ++x)
            for (int y = -1; y <= 1; ++y)
                if (x != 0 || y != 0) {
                    qx = que.front().first + x;
                    qy = que.front().second + y;
                    if (qx >= 1 && qy  >= 1 && qx <= m && qy <= n && mat[qy][qx] == 0) {
                        que.push({qx, qy});
                        mat[qy][qx] = mat[que.front().second][que.front().first] + 1;
                    }
                }
        que.pop();
    }
}

int main() {
    in>>n>>m;
    std::string line;
    in.get();
    for (i = 1; i <= n; ++i) {
        getline(in, line);
        while (m - line.length()) line += ' ';
        for (j = 0; j < m; ++j)
            switch(line[j]) {
            case 'X':
                rMat[i][j + 1] = jMat[i][j + 1] = -1;
                break;
            case ' ':
                rMat[i][j + 1] = jMat[i][j + 1] = 0;
                break;
            case 'R':
                rMat[i][j + 1] = jMat[i][j + 1] = 0;
                ry = i;
                rx = j + 1;
                break;
            case 'J':
                rMat[i][j + 1] = jMat[i][j + 1] = 0;
                jy = i;
                jx = j + 1;
                break;
            }
    }
    BF(rMat, rx, ry);
    BF(jMat, jx, jy);

    tmin = n * m * n;
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            if (rMat[i][j] == jMat[i][j] && rMat[i][j] < tmin && rMat[i][j] > 0) {
                tmin = rMat[i][j];
                result.first = i;
                result.second = j;
            }
    out<<tmin<<" "<<result.first<<" "<<result.second;
    return 0;
}