Cod sursa(job #2125412)

Utilizator skeniaTirla Ovidiu skenia Data 8 februarie 2018 14:19:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>

#define INFINITY 9999999

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

struct Point {
    int line;
    int col;

};

bool notOutOfMatrix(int line, int col);

void uniformSearch(Point start, int costMatrix[101][101]);

int lines, cols;
Point startP, endP;

bool matrix[101][101]; // true - can't get there, false - can get there

int costR[101][101];
int costJ[101][101];

int main() {
    char line[101];
    fin.getline(line, 10);
    istringstream str(line);
    str >> lines >> cols;
    str.clear();
    for (int l = 0; l < lines; ++l) {
        fin.getline(line, cols * 2);
        for (int c = 0; c < cols; ++c) {
            if (line[c] == 'R') {
                startP.line = l;
                startP.col = c;
            } else if (line[c] == 'J') {
                endP.line = l;
                endP.col = c;
            } else if (line[c] == 'X') {
                matrix[l][c] = true;
            }
        }
    }

    for (int l = 0; l < lines; ++l) {
        for (int c = 0; c < cols; ++c) {
            costR[l][c] = INFINITY;
            costJ[l][c] = INFINITY;
        }
    }

    uniformSearch(startP, costR);
    uniformSearch(endP, costJ);

//    for (int l = 0; l < lines; ++l) {
//        for (int c = 0; c < cols; ++c) {
//            fout << costJ[l][c] << ' ';
//        }
//        fout << '\n';
//    }
//    fout << '\n';
//
//    for (int l = 0; l < lines; ++l) {
//        for (int c = 0; c < cols; ++c) {
//            fout << costR[l][c] << ' ';
//        }
//        fout << '\n';
//    }

    Point minPoint = {-1, -1};
    int minCost = INFINITY;
    for (int l = 0; l < lines; ++l) {
        for (int c = 0; c < cols; ++c) {
            if (minCost > costJ[l][c] and costJ[l][c] == costR[l][c] and costJ[l][c] != INFINITY) {
                minPoint = {l, c};
                minCost = costJ[l][c];
            }
        }
    }
    fout << minCost << ' ' << minPoint.line + 1 << ' ' << minPoint.col + 1 << '\n';

    return 0;
}

void uniformSearch(Point start, int costMatrix[101][101]) {
    queue<Point> frontier;
    frontier.push(start);
    costMatrix[start.line][start.col] = 1;

    int dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
    int dy[] = {1, -1, 0, 1, 1, 1, 0, -1};

    while (!frontier.empty()) {
        Point current = frontier.front();
        frontier.pop();

        for (int iter = 0; iter < 8; ++iter) {
            Point next = {current.line + dx[iter], current.col + dy[iter]};
            if (!matrix[next.line][next.col] and notOutOfMatrix(next.line, next.col)) {
                if (costMatrix[next.line][next.col] == INFINITY) {
                    costMatrix[next.line][next.col] = costMatrix[current.line][current.col] + 1;
                    frontier.push(next);
                }
            }
        }
    }

}

bool notOutOfMatrix(int line, int col) {
    return line >= 0 and line < lines and col >= 0 and col < cols;
}