Pagini recente » Cod sursa (job #1040059) | Cod sursa (job #2224542) | Cod sursa (job #2005362) | Cod sursa (job #58846) | Cod sursa (job #2764134)
#include<iostream>
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[]={-1, 0, 1, 0},dj[]={ 0, 1, 0,-1};
int A[205][205], n , m,x,y,X1,Y1,X2,Y2;
int B[205][205];
void Lee1(int istart ,int jstart)
{
queue<pair<int,int>> Q;
Q.push(make_pair(istart , jstart));
A[istart][jstart] = 1;
while(! Q.empty())
{
int i = Q.front().first, j = Q.front().second;
for(int k = 0 ; k < 4 ; k ++)
{
int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
if(iv >= 1 && iv <= n && jv >= 1 && jv <= n // element în matrice
&& A[iv][jv] == 0) // element liber si nemarcat
{
// marcam elementul vecin cu o valoare mai mare
A[iv][jv] = A[i][j] + 1;
// il adaugam in coada
Q.push(make_pair(iv , jv));
}
}
Q.pop(); // eliminam din coada
}
}
void Lee2(int istart ,int jstart)
{
queue<pair<int,int>> Q1;
Q1.push(make_pair(istart , jstart));
B[istart][jstart] = 1;
while(! Q1.empty())
{
int i = Q1.front().first, j = Q1.front().second;
for(int k = 0 ; k < 4 ; k ++)
{
int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
if(iv >= 1 && iv <= n && jv >= 1 && jv <= n // element în matrice
&& B[iv][jv] == 0) // element liber si nemarcat
{
// marcam elementul vecin cu o valoare mai mare
B[iv][jv] = B[i][j] + 1;
// il adaugam in coada
Q1.push(make_pair(iv , jv));
}
}
Q1.pop(); // eliminam din coada
}
}
int main()
{
fin>>n>>m;
fin.get();
for(int i=1;i<=n;i++)
{
char ch[205];
strcpy(ch,"");
fin.getline(ch,205);
for(int j=1;j<=m;j++)
{
//notam X cu -1
if(ch[j-1]=='X')
{
A[i][j]=-1;
B[i][j]=-1;
}
if(ch[j-1]=='R')
{
X1=i;
Y1=j;
}
if(ch[j-1]=='J')
{
X2=i;
Y2=j;
}
}
}
Lee1(X1,Y1);
Lee2(X2,Y2);
int minn=2000000000;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(A[i][j]==B[i][j] && A[i][j]!=-1 && A[i][j]!=0)
{
if(A[i][j]<minn)
{
minn=A[i][j];
}
}
}
fout<<minn-1<<"\n";
fin.close();
fout.close();
return 0;
}