Cod sursa(job #1982687)

Utilizator calin13Calin Nicolau calin13 Data 19 mai 2017 21:51:32
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

typedef vector<string>      Harta;
typedef vector<vector<int>> Distante;

struct Coord {
    Coord(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
    int x, y;
};

template<typename T>
void initMatrice(int lin, int col, T& matrice)
{
    matrice.resize(lin);
    for (auto& it : matrice) {
        it.resize(col);
    }
}

void bf(const Coord &start, const Harta &harta, Distante &dist)
{
    queue<Coord> q;
    q.push(start);
    int n = harta.size();
    int m = harta[0].size();
    
    while (!q.empty()) {
        Coord pos = q.front();
        q.pop();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int x = pos.x + j;
                int y = pos.y + i;
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    if (dist[y][x] == 0 && x != start.x && y != start.y) {
                        if (harta[y][x] != 'X') {
                            dist[y][x] = dist[pos.y][pos.x] + 1;
                            q.push(Coord(x, y));
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream fin("rj.in");
    ofstream fout("rj.out");

    int n, m;
    fin >> n >> m;
    fin.get();

    Coord startR, startJ;
    Harta harta(n);
    for (int i = 0; i < n; i++) {
        string line;
        getline(fin, line);
        harta[i] = line;
        for (int j = 0; j < m; j++) {
            if (harta[i][j] == 'R') {
                startR = Coord(j, i);
            } else if (harta[i][j] == 'J') {
                startJ = Coord(j, i);
            }
        }
    }

    Distante distR, distJ;
    initMatrice(n, m, distR);
    initMatrice(n, m, distJ);
    bf(startR, harta, distR);
    bf(startJ, harta, distJ);

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++) {
    //         cout << distR[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++) {
    //         cout << distJ[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    Coord posMin(-1, -1);
    int distMin = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (distR[i][j] == 0) {
                continue;
            }
            if (distR[i][j] == distJ[i][j]) {
                int dist = distR[i][j];
                if ((posMin.x == -1 && posMin.y == -1) 
                        || (distMin > dist)
                        || ((distMin == dist) && ((i < posMin.y || (i == posMin.y && j < posMin.x))))) {
                    posMin = Coord(j, i);
                    distMin = dist;
                }
            }
        }
    }
    fout << distMin + 1<< " " << posMin.y + 1<< " " << posMin.x + 1;

    fin.close();
    fout.close();
    return 0;
}