Cod sursa(job #2211918)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 12 iunie 2018 15:09:30
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int N, M, x, y, R[103][103], J[103][103];
char a[103][103];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1},
    dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

queue<pair<int, int>> q;
int lee(int xs, int ys, int A[103][103]) {
    while(!q.empty()) q.pop();
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            A[i][j] = 0;
    for(int i = 0; i <= N + 1; i++)
        A[i][0] = A[i][M + 1] = -1;
    for(int i = 0; i <= M + 1; i++)
        A[0][i] = A[N + 1][i] = -1;
    A[xs][ys] = 1;
    q.push({xs, ys});
    while(!q.empty()) {
        int i = q.front().first, j = q.front().second;
        for(int s = 0; s < 8; s++) {
            int ii = i + dx[s], jj = j + dy[s];
            if (a[ii][jj] == ' ' && A[ii][jj] == 0) A[ii][jj] = A[i][j] + 1, q.push({ii, jj});
        }
        q.pop();
    }
    return -1;
}
int main()
{
    f >> N >> M;
    f.get();
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M + 1; j++)
            f.get(a[i][j]);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) {
            if(a[i][j] == 'R') lee(i, j, R);
            else if(a[i][j] == 'J') lee(i, j, J);
        }
    int MIN = INT_MAX;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(R[i][j] == J[i][j] && a[i][j] != 'R' && a[i][j] != 'J' && a[i][j] != 'X' && R[i][j] > 0 && MIN > R[i][j]) {
                MIN = R[i][j];
                x = i;
                y = j;
            }
    g << MIN << " " << x << " " << y << " " << "\n";
    return 0;
}