Cod sursa(job #2197574)

Utilizator Andreea_DanielaAndreea Guster Andreea_Daniela Data 22 aprilie 2018 15:18:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int di[8] = {0, 0,  1, -1, 1, -1, -1,  1};
int dj[8] = {1, -1, 0, 0,  1, 1 , -1, -1};
int n, m, matR[150][150], matJ[150][150];
int R_i, R_j, J_i, J_j;

void citire( ifstream &f)
{
    int i,j;
    f>>n>>m;

   string str;
   char c;
   f.get(c);  //citesc endl dupa m

   i = 1;  j = 1;
   while(getline(f, str))    //citesc matricea
   {
       for(string::iterator it=str.begin(); it!=str.end(); ++it)
       {
         c= *it;// cout<<c;
         if( c == 'R') {R_i = i;  R_j = j;}
         else
            if( c == 'J')  {J_i = i; J_j = j;}
         else
         if( c == 'X')  {matR[i][j] = -1;  matJ[i][j] = -1;}

         j++;
       }
       i++; j=1;
       //cout<<endl;
   }
}

//algoritmul lui lee: un alg ce det nr de pasi ot a ajunge din pct x in pct y in anumite conditii
//alg lui lee este de fapt un BFS doar ca e aplicat pe o grila, pe o mat
//complex O(n*m)

bool coord_Ok(int i, int j, int mat[][150])
{
    if(i < 1 || j < 1 || i > n || j> m)
        return false;
    if(mat[i][j] == -1)    //daca a intalnit obstacolul
        return false;

    return true;
}

void Lee(int x, int y, int mat[][150])
{

   queue< pair<int, int> > c;
   int i, j, i_urmator,j_urmator;

   c.push( make_pair(x, y) );
   mat[x][y] = 1;

   while( !(c.empty()) )
   {
       i = c.front().first;
       j = c.front().second;
       c.pop();

       for(int directie = 0; directie < 8; directie++)
       {
           i_urmator = i + di[directie];
           j_urmator = j + dj[directie];
           if( coord_Ok(i_urmator, j_urmator, mat) && mat[i_urmator][j_urmator] < 1)
           {
               mat[i_urmator][j_urmator] = mat[i][j] + 1;
               c.push(make_pair(i_urmator, j_urmator));
           }
       }
   }
}

int main()
{
    ifstream f("rj.in");
    citire( f);
    f.close();

    Lee(R_i, R_j, matR);
    Lee(J_i, J_j, matJ);

    int i, j, Min, px, py;
/*
    for(i= 1; i<= n; i++)
    {for(j= 1; j<= m; j++)
    cout<<matR[i][j]<<" ";
    cout<<endl;}

    cout<<endl;
      for(i= 1; i<= n; i++)
    {for(j= 1; j<= m; j++)
    cout<<matJ[i][j]<<" ";
    cout<<endl;}

*/
   for(i= 1 ; i<= n; i++)
    for(j= 1; j<= m; j++)
     if(matR[i][j] == matJ[i][j] && matR[i][j] > -1)
    {
        Min = matR[i][j];
        px = i;
        py = j;
    }


    ofstream fout("rj.out");
    fout<<Min<<" "<<px<<" "<<py;
    fout.close();

    return 0;
}