Pagini recente » Cod sursa (job #1930699) | Cod sursa (job #2452041) | Cod sursa (job #2962099) | Cod sursa (job #2708577) | Cod sursa (job #2197574)
#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;
}