Pagini recente » Cod sursa (job #814054) | Cod sursa (job #2805138) | Cod sursa (job #1339226) | Cod sursa (job #622726) | Cod sursa (job #2684222)
#include <fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
const int MAXN = 100;
const int MAXM = 100;
struct Celula
{
int l, c;
};
char matrice[MAXN + 1][MAXM + 1];
int distanta_r[MAXN + 1][MAXM + 1] , distanta_j[MAXN + 1][MAXM + 1];
Celula parinte[MAXN + 1][MAXM + 1];
Celula coada[MAXN * MAXM + 5];
int main()
{
int M , N, linie_s_j,coloana_s_j,linie_s_r ,coloana_s_r ,x , y;
in >> N >> M;
in.get();
int st, dr;
for(int i = 1;i <= N;i ++)
{
in.get(matrice[i] + 1,M + 5);
in.get();
for(int j = 1;j <= M;j ++)
{
if(matrice[i][j] == 'R')
{
linie_s_r = i;
coloana_s_r = j;
}
else if(matrice[i][j] == 'J')
{
linie_s_j = i;
coloana_s_j = j;
}
}
}
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int x_vecin , y_vecin ;
Celula start;
start.l = linie_s_r;
start.c = coloana_s_r;
coada[1] = start;
st = dr = 1;
distanta_r[linie_s_r][coloana_s_r] = 1;
while (st <= dr)
{
Celula curent = coada[st];
int x = curent.l;
int y = curent.c;
for (int d = 0; d < 4; ++d)
{
int x_vecin = x + dx[d];
int y_vecin = y + dy[d];
if (1 <= x_vecin && x_vecin <= N && 1 <= y_vecin && y_vecin <= M && matrice[x_vecin][y_vecin] != 'X' && distanta_r[x_vecin][y_vecin] == 0)
{
distanta_r[x_vecin][y_vecin] = distanta_r[x][y] + 1;
parinte[x_vecin][y_vecin] = curent;
Celula vecin;
vecin.l = x_vecin, vecin.c=y_vecin;
dr++;
coada[dr] = vecin;
}
}
st++; //il scoatem pe curent din coada
}
start.l = linie_s_j;
start.c = coloana_s_j;
coada[1] = start;
st = dr = 1;
distanta_j[linie_s_j][coloana_s_j] = 1;
while (st <= dr)
{
Celula curent = coada[st];
int x = curent.l;
int y = curent.c;
for (int d = 0; d < 4; ++d)
{
int x_vecin = x + dx[d];
int y_vecin = y + dy[d];
if (1 <= x_vecin && x_vecin <= N && 1 <= y_vecin && y_vecin <= M && matrice[x_vecin][y_vecin] != 'X' && distanta_j[x_vecin][y_vecin] == 0)
{
distanta_j[x_vecin][y_vecin] = distanta_j[x][y] + 1;
parinte[x_vecin][y_vecin] = curent;
Celula vecin;
vecin.l = x_vecin, vecin.c=y_vecin;
dr++;
coada[dr] = vecin;
}
}
st++; //il scoatem pe curent din coada
}
int timp = 1000000, lcelula, ccelula;
for(int i = 1;i <= N;i ++)
for(int j = 1;j <= M;j ++)
if(distanta_r[i][j] == distanta_j[i][j] && distanta_r[i][j] < timp && distanta_r[i][j] != 0)
{
timp = distanta_r[i][j];
lcelula = i;
ccelula = j;
}
out << timp - 1 <<" "<< lcelula <<" "<< ccelula;
return 0;
}