Cod sursa(job #2916458)

Utilizator DavidLDavid Lauran DavidL Data 29 iulie 2022 20:22:29
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("rj.in");
ofstream fo("rj.out");

const int NMAX = 105;
const int INF = 1e9;

const int dl[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, m;
char M[NMAX][NMAX];
int x[2], y[2];
int dist[2][NMAX][NMAX];

inline bool val(int lin, int col) {
    return 1 <= lin && lin <= n && 1 <= col && col <= m;
}

void bfs(int ind) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dist[ind][i][j] = INF;

    queue <pair<int, int>> Q;

    dist[ind][x[ind]][y[ind]] = 0;
    Q.push({x[ind], y[ind]});

    while (!Q.empty()) {
        int lin = Q.front().first, col = Q.front().second;
        Q.pop();

        for (int d = 0; d < 8; d++) {
            int ln = lin + dl[d], cn = col + dc[d];
            if (val(ln, cn) && M[ln][cn] == ' ' && 1 + dist[ind][lin][col] < dist[ind][ln][cn]) {
                dist[ind][ln][cn] = 1 + dist[ind][lin][col];
                Q.push({ln, cn}); // incearca sa imbunatatesti
            }
        }
    }
}

int main()
{
    fi >> n >> m;
    fi.getline(M[0] + 1, 102);

    for (int i = 1; i <= n; i++) {
        fi.getline(M[i] + 1, 102);
        for (int j = 1; j <= m; j++) {
            if (M[i][j] == 'R')
                x[0] = i, y[0] = j;
            else if (M[i][j] == 'J')
                x[1] = i, y[1] = j;
        }
    }

    bfs(0);
    bfs(1);

    int ansx = -1, ansy = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (dist[0][i][j] == dist[1][i][j] && (ansx == -1 || dist[0][i][j] < dist[0][ansx][ansy]))
                ansx = i, ansy = j;

    fo << dist[0][ansx][ansy] + 1 << " " << ansx << " " << ansy;

    return 0;
}