Cod sursa(job #2449257)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 19 august 2019 01:14:01
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <queue>
using namespace std;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1,  0}, dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1}, n, m, x1, y1, a[101][101], b[101][101], minim = 10000000;

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

struct punct{
    int x, y;
};

queue<punct> q;

void citire() {
    char s[102];
    f >> n >> m;
    f.getline(s, 101);
    for(int i  = 1; i <= n; i++) {
        f.getline(s, 101);
        for(int j = 1; j <= m; j++) {
            if(s[j-1] == 'R') {
                a[i][j] = -1;
                q.push({i, j});
            } else if(s[j-1] == 'J')
                x1 = i, y1 = j;
            else if(s[j-1] == 'X')
                a[i][j] = -2;
        }
    }
}

bool ok(punct w, int a[][101]) {
    if(w.x < 1 || w.y < 1 || w.x > n || w.y > m)
        return false;
    if(a[w.x][w.y])
        return false;
    return true;
}

void lee(int a[][101]) {
    while(!q.empty()) {
        punct current = q.front();
        for(int k = 0; k < 8; k++) {
            punct next;
            next.x = current.x + dx[k];
            next.y = current.y + dy[k];
            if(ok(next, a)) {
                if(a[current.x][current.y] == -1)
                    a[next.x][next.y] = 1;
                else
                    a[next.x][next.y] = a[current.x][current.y]+1;
                q.push(next);
            }
        }
        q.pop();
    }
}

int main() {
    citire();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(a[i][j] != -1)
                b[i][j] = a[i][j];
    b[x1][y1] = -1;

    lee(a);
    q.push({x1, y1});
    lee(b);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(a[i][j] == b[i][j] && a[i][j] > 0 && a[i][j] < minim) {
                minim = a[i][j];
                x1 = i;
                y1 = j;
            }

    g << minim+1 << ' ' << x1 << ' ' << y1;
}