# Cod sursa(job #2674976)

Utilizator Data 20 noiembrie 2020 22:58:50 Rj 0 cpp-64 done Arhiva de probleme 2.58 kb
``````#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("rj.in");
ofstream out("rj.out");

int n,m;
pair<int, int> start;

int coordx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int coordy[] = {0, 1, 0, -1, 1, 1, -1, -1};

void afis(int n, int m, vector<vector<int> > mat)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
}

vector<vector<int> > bfs(pair<int, int> start, vector<vector<int> > mat, int finish)
{
vector<vector<int> > viz(n, vector<int> (m, 0));
vector<vector<int> > dis(n, vector<int> (m, 0));
queue<pair<int, int> > q;
q.push(start);
viz[start.first][start.second] = 1;

while(!q.empty())
{
pair<int, int> varf = q.front();
q.pop();
for(int i=0; i<8; i++)
{
int pozx = varf.first + coordx[i];
int pozy = varf.second + coordy[i];
if(pozx >=0 && pozx < n && pozy >=0 && pozy < m &&
viz[pozx][pozy] == 0 && mat[pozx][pozy] != -1)
{
viz[pozx][pozy] = 1;
q.push(make_pair(pozx, pozy));
dis[pozx][pozy] = dis[varf.first][varf.second] + 1;

if(mat[pozx][pozy] == finish)
{
return dis;
}
}
}
}
}

int main()
{
in>>n>>m;
vector<vector<int> > jul(n+1, vector<int> (m+1, 0));
vector<vector<int> > rom(n+1, vector<int> (m+1, 0));

vector<vector<int> > disJ(n+1, vector<int> (m+1, 0));
vector<vector<int> > disR(n+1, vector<int> (m+1, 0));
pair<int, int> startJ, startR;
in.get();
for(int i=0; i<n; i++)
{
char s[150];
in.getline(s,150);
for(int j=0; j<m; j++)
{
if(s[j] == 'R')
{
startR = make_pair(i, j);
jul[i][j] = rom[i][j] = 2;
}
else if(s[j] == 'J')
{
startJ = make_pair(i, j);
jul[i][j] = rom[i][j] = 1;
}
else if(s[j] == 'X')
{
jul[i][j] = rom[i][j] = -1;
}
else jul[i][j] = rom[i][j] = 0;
}
}

disJ = bfs(startJ, jul, 2);
disR = bfs(startR, rom, 1);

for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(disJ[i][j] == disR[i][j] && disJ[i][j] != 0)
out<<disJ[i][j]+1<<" "<<i+1<<" "<<j+1;

return 0;
}
``````