Cod sursa(job #2668281)

Utilizator CharmichlesAndrei Brihac Charmichles Data 4 noiembrie 2020 18:46:47
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

const int NMAX = 101;

int n, m, xr, yr, xj, yj, dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}, ar[NMAX][NMAX], aj[NMAX][NMAX];
char a[NMAX][NMAX];

struct punct {
    int x;
    int y;
} q[NMAX * NMAX];

bool isOk(punct p) {
    return p.x >= 1 && p.x <= n && p.y >= 1 && p.y <= m;
}

void lee(int m[NMAX][NMAX], int xs, int ys) {
    int stg = 1, dr = 0;
    punct p;
    p.x = xs;
    p.y = ys;
    q[++dr] = p;
    m[xs][ys] = 0;
    while (stg <= dr) {
        p = q[stg];
        for (int i = 0; i < 8; i++) {
            punct new_p = p;
            new_p.x += dx[i];
            new_p.y += dy[i];
            if (new_p.x == xs && new_p.y == ys) {
                continue;
            }
            if (m[new_p.x][new_p.y] == -1 && a[new_p.x][new_p.y] != 'X' && isOk(new_p)) {
                q[++dr] = new_p;
                m[new_p.x][new_p.y] = m[p.x][p.y] + 1;
            }
        }
        stg++;
    }
}

int main() {
    fin >> n >> m;
    string temp;
    getline(fin, temp);
    for (int i = 1; i <= n; i++) {
        string line;
        getline(fin, line);
        for (unsigned int j = 0; j < line.size(); j++) {
            if (line[j] == 'R') {
                xr = i;
                yr = j + 1;
            }
            if (line[j] == 'J') {
                xj = i;
                yj = j + 1;
            }
            a[i][j + 1] = line[j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ar[i][j] = -1;
            aj[i][j] = -1;
        }
    }

    fin.close();

    lee(ar, xr, yr);
    lee(aj, xj, yj);

    int xmin = n + 1, ymin = m + 1, costmin = NMAX * NMAX + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ar[i][j] == aj[i][j] && ar[i][j] != -1) {
                if (ar[i][j] < costmin) {
                    costmin = ar[i][j];
                    xmin = i;
                    ymin = j;
                }
                else if (ar[i][j] == costmin) {
                    if (i < xmin) {
                        xmin = i;
                        ymin = j;
                    }
                    else if (i == xmin && j < ymin) {
                        xmin = i;
                        ymin = j;
                    }
                }
            }
        }
    }

    fout << costmin + 1 << ' ' << xmin << ' ' << ymin << '\n';

    fout.close();
    return 0;
}