Cod sursa(job #2124583)

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

using namespace std;

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

struct Point {
    int line;
    int col;
};

int lines, cols;
Point startP, endP;
bool matrix[101][101]; // true - can't get there, false - can get there
Point cameFrom[101][101];

int main() {
    int lines, cols;
    char line[101];
    fin.getline(line, 10, '\n');
    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;
            }
        }
    }

    queue<Point> frontier;
    frontier.push(startP);
    for (int l = 0; l < lines; ++l) {
        for (int c = 0; c < cols; ++c) {
            cameFrom[l][c] = {-1, -1};
        }
    }

    cameFrom[startP.line][startP.col] = {-2, -2};
//    cameFrom[endP.line][endP.col] = {-2, -2};

    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();

        if (current.line == endP.line and current.col == endP.col) {
            break;
        }

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

    Point current = endP;
    int time = 0;
    Point history[10005];
    history[0] = current;
    while (current.line != startP.line and current.col != startP.col) {
        current = cameFrom[current.line][current.col];
        time++;
        history[time] = current;
    }
    int ind = time / 2;
    if(time % 2 == 1)
        time++;
    fout << time / 2 + 1 << ' ' << history[ind].line + 1 << ' ' << history[ind].col + 1 << '\n';
//
//    for (int l = 0; l < lines; ++l) {
//        for (int c = 0; c < cols; ++c) {
//            cout << '(' << cameFrom[l][c].line << ',' << cameFrom[l][c].col << ") ";
//        }
//        cout << '\n';
//    }
//    cout << startP.line << ' ' << startP.col << '\n';
//    cout << endP.line << ' ' << endP.col << '\n';
    return 0;
}