Cod sursa(job #1726365)

Utilizator cristina_borzaCristina Borza cristina_borza Data 7 iulie 2016 20:29:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <set>

#define se second
#define fi first

using namespace std;

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

int dx[] = {-1 , -1 , -1 , 0 , 0 , 1 , 1 , 1};
int dy[] = {-1 , 0 , 1 , -1 , 1 , -1 , -0 , 1};

int n , m , lj , cj , lr , cr , sol =  100005 , ls , cs;
int mat[3][105][105];

char sir[200];
char ch;

queue <pair <int , int> > coada;

void lee(int type , int lin , int col);

int main() {
    f >> n >> m;
    f.get();
    for (int i = 1; i <= n; ++i) {
        f.getline(sir + 1 , 200 , '\n');
        for (int j = 1; j <= m; ++j) {
            ch = sir[j];
            if (ch == 'J') {
                lj = i;
                cj = j;
            }

            if (ch == 'R') {
                lr = i;
                cr = j;
            }

            if (ch == 'X') {
                mat[1][i][j] = mat[2][i][j] = -1;
            }
        }
    }

    lee(1 , lj , cj);
    lee(2 , lr , cr);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mat[1][i][j] == mat[2][i][j] && mat[2][i][j] > 0) {
                if (mat[1][i][j] < sol) {
                    sol = mat[1][i][j];
                    ls = i;
                    cs = j;
                }
            }
        }
    }

    g << sol << " " << ls << " " << cs;
    return 0;
}

void lee(int type , int lin , int col) {
    while (!coada.empty()) {
        coada.pop();
    }

    coada.push(make_pair(lin , col));
    mat[type][lin][col] = 1;

    while (!coada.empty()) {
        pair <int , int> aux = coada.front();
        coada.pop();

        for (int i = 0; i < 8; ++i) {
            if (aux.fi + dx[i] > n || aux.fi + dx[i] < 1)
                continue;

            if (aux.se + dy[i] > m || aux.se + dy[i] < 1)
                continue;

            if (mat[type][aux.fi + dx[i]][aux.se + dy[i]] == 0) {
                mat[type][aux.fi + dx[i]][aux.se + dy[i]] = mat[type][aux.fi][aux.se] + 1;
                coada.push(make_pair(aux.fi + dx[i] , aux.se + dy[i]));
            }
        }
    }
}