Pagini recente » Cod sursa (job #797662) | Cod sursa (job #2667563)
#include <iostream>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
struct punct { int linie, coloana;} R, J;
char matrice[101][101];
int n, m, mr[101][101], mj[101][101];
int minim = INT_MAX;
punct coordonate_min;
queue<punct> coada;
void citire() {
string rand;
f>>n>>m;
getline(f, rand);
for(int i=1; i<=n; i++) {
getline(f, rand);
if(rand.length() < m)
rand = rand + ' ';
for (int j = 1; j <= m; j++) {
matrice[i][j] = rand[j - 1];
if (matrice[i][j] == 'R')
R.linie=i, R.coloana=j;
if (matrice[i][j] == 'J')
J.linie=i, J.coloana=j;
}
}
}
void bfs_r() {
while(!coada.empty()) {
punct crt = coada.front();
coada.pop();
int i, j;
punct x;
for(i=-1; i<=1; i++)
for(j=-1; j<=1; j++)
if(!(i==0 && j==0)) {
x.linie = crt.linie + i;
x.coloana = crt.coloana + j;
if(matrice[x.linie][x.coloana] == ' ' && mr[x.linie][x.coloana] == 0) {
mr[x.linie][x.coloana] = mr[crt.linie][crt.coloana] + 1;
coada.push(x);
}
}
}
}
void bfs_j() {
while(!coada.empty()) {
punct crt = coada.front();
coada.pop();
int i, j;
punct x;
for(i=-1; i<=1; i++)
for(j=-1; j<=1; j++)
if(!(i==0 && j==0)) {
x.linie = crt.linie + i;
x.coloana = crt.coloana + j;
if(matrice[x.linie][x.coloana] == ' ' && mj[x.linie][x.coloana] == 0) {
mj[x.linie][x.coloana] = mj[crt.linie][crt.coloana] + 1;
coada.push(x);
}
}
}
}
void intalnire() {
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if (mr[i][j] == mj[i][j] && mr[i][j] > 0)
if (mr[i][j] < minim) {
minim = mr[i][j];
coordonate_min.linie = i;
coordonate_min.coloana = j;
}
}
int main() {
citire();
coada.push(R);
mr[R.linie][R.coloana]=1;
bfs_r();
while (!coada.empty())
coada.pop();
coada.push(J);
mj[J.linie][J.coloana]=1;
bfs_j();
// for(int i=1; i<=n; i++){
// for(int j=1; j<=m; j++)
// if (matrice[i][j] == ' ')
// cout<<mr[i][j]<<" ";
// else
// cout<<matrice[i][j]<<" ";
// cout<<endl;
// }
//
// cout<<"________________________"<<endl;
//
// for(int i=1; i<=n; i++){
// for(int j=1; j<=m; j++)
// if (matrice[i][j] == ' ')
// cout<<mj[i][j]<<" ";
// else
// cout<<matrice[i][j]<<" ";
// cout<<endl;
// }
intalnire();
g<<minim<<" "<<coordonate_min.linie<<" "<<coordonate_min.coloana;
}