Pagini recente » Cod sursa (job #827421) | Cod sursa (job #2772791) | Cod sursa (job #301825) | Cod sursa (job #973495) | Cod sursa (job #549317)
Cod sursa(job #549317)
#include<fstream>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
ofstream fout("rj.out");
#define mp make_pair
void read();
void solve();
int R[105][105], J[105][105];
char a[105][105];
int n, m;
const int dx[] = {0, 1, 0, -1, -1, 1, -1, 1},
dy[] = {1, 0, -1, 0, -1, 1, 1,-1};
queue< pair<pair<int , int> , int> > Q, Q1;
int iR, jR;
int iJ, jJ;
int main()
{
read();
solve();
return 0;
}
void read()
{
ifstream fin("rj.in");
fin >> n >> m;
char c[150];
fin.get();
for(int i = 0; i < n; ++i)
{
fin.getline( c, 150);
strcpy(a[i], c);
}
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if( a[i][j] == 'R' ) { iR = i; jR = j; };
if( a[i][j] == 'J' ) { iJ = i; jJ = j; };
}
fin.close();
}
void solve()
{
//ROMEO
Q.push( mp( mp(iR, jR), 0) );
R[iR][jR] = -1;
while( !Q.empty() )
{
int l = Q.front().first.first;
int c = Q.front().first.second;
int d = Q.front().second;
for(int k = 0; k < 8; ++k)
{
int l1 = l + dx[k];
int c1 = c + dy[k];
if( a[l1][c1] == ' ' && !R[l1][c1] && l1 >= 0 && l1 < n && c1 >= 0 && c1 < m)
{
Q.push( mp( mp(l1, c1), d + 1) );
R[l1][c1] = d + 1;
}
}
Q.pop();
}
//JULIETA
Q1.push( mp( mp(iJ, jJ), 0) );
J[iJ][jJ] = -1;
while( !Q1.empty() )
{
int l = Q1.front().first.first;
int c = Q1.front().first.second;
int d = Q1.front().second;
for(int k = 0; k < 8; ++k)
{
int l1 = l + dx[k];
int c1 = c + dy[k];
if( a[l1][c1] == ' ' && !J[l1][c1] && l1 >= 0 && l1 < n && c1 >= 0 && c1 < m)
{
Q1.push( mp( mp(l1, c1), d + 1) );
J[l1][c1] = d + 1;
}
}
Q1.pop();
}
//AFISARE
int is, js, minim = 10000000;
for( int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if( R[i][j] == J[i][j] && R[i][j] < minim && R[i][j] != 0)
{
minim = R[i][j];
is = i;
js = j;
}
fout << minim + 1 << " " << is + 1 <<" "<< js + 1;
}