Cod sursa(job #1707237)

Utilizator cameleonGeorgescu Dan cameleon Data 24 mai 2016 17:50:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include<cstring>
#include<queue>
#include<iomanip>
#define Nmax 105
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
int dx[] = {-1,-1,-1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0,-1,-1};
struct pozitie{
    int l,c;
};
int R[Nmax][Nmax], J[Nmax][Nmax], n, m, Lmin = 100000;
int i,j, xj, yj, xr, yr, x, y;
char s[Nmax];
queue <pozitie> q;

void make_poz(int x, int y, pozitie &t){
    t.l = x, t.c = y;
}
void Lee(int x, int y, int a[Nmax][Nmax]){

    pozitie t, tnou;

    make_poz(x,y,t);
    q.push(t);
    while(!q.empty()){

        t = q.front();
        q.pop();

        for(int i = 0; i < 8; i++){
            x = t.l + dx[i];
            y = t.c + dy[i];

            if(a[x][y] == 0){
                a[x][y] = a[t.l][t.c]+1;
                make_poz(x,y,tnou);
                q.push(tnou);
            }
        }
    }
}

int main()
{
    fin>>n >> m;

    fin.get();
    for(i =  1; i <= n; i++){

        fin.getline(s+1,105);
        for(j = 1; j <= m; j++){
            if(s[j] == 'R')
                xr = i, yr = j, R[i][j] = 1;
            if(s[j] == 'J')
                xj = i, yj = j, J[i][j] = 1;
            if(s[j] == 'X')
                R[i][j] = J[i][j] = -1;
        }
    }

    //bordare matrici
    for(i = 0; i <= n+1; i++)
        R[i][0] = R[i][m+1] = J[i][0] = J[i][m+1] = -1;
    for(j = 1; j <= m; j++)
        R[0][j] = R[n+1][j] = J[0][j] = J[n+1][j] = -1;

    //parcurgeri matrici
    Lee(xr,yr, R);
    Lee(xj,yj,J);

    //determinare punct de intalnire
    for(i = 1; i <= n; i++)
        for(j =1; j <= m; j++)
            if(R[i][j] > 0 && R[i][j] == J[i][j] && R[i][j] < Lmin){
                Lmin = R[i][j];
                x =i; y =j;
            }

    fout<<Lmin<<" "<<x<< " "<<y<<"\n";

    return 0;
}