Pagini recente » Cod sursa (job #2698462) | Cod sursa (job #3184994) | Cod sursa (job #2937273) | Cod sursa (job #3272063) | Cod sursa (job #2716816)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
int n, m;
char s[107];
int v[103][103];
int viz1[103][103];
int viz2[103][103];
int linJ, colJ, linR, colR;
queue < pair < int, int > > q;
int dx[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
int l, c;
int mn = 10137;
int main()
{
in >> n >> m;
in.getline ( s, 137 );
for ( int i = 1 ; i <= n ; ++i )
{
in.getline ( s, 137 );
for ( int j = 0 ; j < m ; ++j )
{
if ( s[j] == ' ' )
v[i][j + 1] = 1;
else if ( s[j] == 'X' )
v[i][j + 1] = 0;
else if ( s[j] == 'J' )
{
linJ = i;
colJ = j + 1;
v[i][j + 1] = 1;
}
else if ( s[j] == 'R' )
{
linR = i;
colR = j + 1;
v[i][j + 1] = 1;
}
}
}
/*for ( int i = 0 ; i <= n + 1 ; ++i )
for ( int j = 0 ; j <= m + 1 ; ++j )
v2[i][j] = v[i][j];*/
/*for ( register int i = 0 ; i <= n + 1 ; ++i )
{
for ( register int j = 0 ; j <= m + 1 ; ++j )
out << v[i][j] << " ";
out << '\n';
}*/
///romeo
q.push ( { linR, colR } );
viz1[linR][colR] = 1;
while ( !q.empty () )
{
l = q.front ().first;
c = q.front ().second;
q.pop ();
for ( int i = 1 ; i <= 8 ; ++i )
if ( v[l + dx[i]][c + dy[i]] && !viz1[l + dx[i]][c + dy[i]] )
{
viz1[l + dx[i]][c + dy[i]] = viz1[l][c] + 1;
q.push ( { l + dx[i], c + dy[i] } );
}
}
/*for ( register int i = 0 ; i <= n + 1 ; ++i )
{
for ( register int j = 0 ; j <= m + 1 ; ++j )
out << viz1[i][j] << " ";
out << '\n';
}*/
///julieta
q.push ( { linJ, colJ } );
viz2[linJ][colJ] = 1;
while ( !q.empty () )
{
l = q.front ().first;
c = q.front ().second;
q.pop ();
for ( register int i = 1 ; i <= 8 ; ++i )
if ( v[l + dx[i]][c + dy[i]] && !viz2[l + dx[i]][c + dy[i]] )
{
viz2[l + dx[i]][c + dy[i]] = viz2[l][c] + 1;
q.push ( { l + dx[i], c + dy[i] } );
}
}
/*for ( register int i = 0 ; i <= n + 1 ; ++i )
{
for ( register int j = 0 ; j <= m + 1 ; ++j )
out << viz2[i][j] << " ";
out << '\n';
}*/
for ( register int i = 1; i <= n ; ++i )
for ( register int j = 1 ; j <= m ; ++j )
if ( viz1[i][j] && viz1[i][j] == viz2[i][j] )
{
if ( mn > viz1[i][j] )
{
mn = viz1[i][j];
l = i;
c = j;
}
}
out << mn << " " << l << " " << c;
return 0;
}