Pagini recente » Cod sursa (job #487033) | Cod sursa (job #866153) | Cod sursa (job #1004765) | Cod sursa (job #1614939) | Cod sursa (job #2764149)
#include<iostream>
#include<fstream>
#include<queue>
#include<string.h>
#include<iomanip>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int di[8]={-1,-1,-1,0,1,1,1,0};
int dj[8]={-1,0,1,1,1,0,-1,-1};
int A[205][205], n , m,x,y,X1,Y1,X2,Y2,pozi,pozj;
int B[205][205];
char ch[105];
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 < 8 ; k ++)
{
int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m // 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 < 8 ; k ++)
{
int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m // 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();
fin.get();
for(int i=1;i<=n;i++)
{
strcpy(ch,"");
fin.getline(ch,105);
//cout<<ch<<"***\n";
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);
//debugging=hell
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<setw(3)<<A[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n\n";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<setw(3)<<B[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n\n";
*/
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];
pozi=i;
pozj=j;
}
}
}
fout<<minn<<" "<<pozi<<" "<<pozj;
fin.close();
fout.close();
return 0;
}