Pagini recente » Cod sursa (job #1968231) | Cod sursa (job #2218384) | Cod sursa (job #241693) | Cod sursa (job #2247906) | Cod sursa (job #661104)
Cod sursa(job #661104)
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[] = { 1, 0, -1, 0, -1, 1, 1, -1 },
dj[] = { 0, -1, 0, 1, 1, 1, -1, -1 };
struct poz{
int x;
int y;
};
#define INF 0x3f3f3f3f
int a[101][101];
int b[101][101];
char str[200];
poz v[200];
char y;
int n, m, ir ,ij ,jr, jj;
int iv, jv;
bool Inside(int i, int j);
int main()
{
fin >> n >> m;
fin.getline(str, 200);
for ( int i = 1; i <= n; i++ )
{
fin.getline(str, 200);
for( int j = 1; j <= m; j++ )
{
if ( str[j-1] == 'R' )
{
a[i][j] = 1;
ir = i;
jr = j;
}
else if ( str[j-1] == 'J' )
{
b[i][j] = 1;
ij = i;
jj = j;
}
else if( str[j-1] == 'X' )
{
a[i][j] = -1;
b[i][j] = -1;
}
}
}
int i, j;
/*for ( i = 1; i <= n; i++ )
{
for( j = 1; j <= m; j++ )
fout << a[i][j]<< ' ';
fout << '\n';
}
fout << '\n';
for ( i = 1; i <= n; i++ )
{
for( j = 1; j <= m; j++ )
fout << b[i][j]<< ' ';
fout << '\n';
}
fout << '\n';
*/
queue<pair<int,int> > Q;
Q.push(make_pair(ir, jr));
while ( !Q.empty() )
{
i = Q.front().first;
j = Q.front().second;
//fout << i << ' ' << j << '\n';
Q.pop();
for ( int d = 0; d < 8; ++d )
{
iv = i + di[d];
jv = j + dj[d];
if ( Inside(iv, jv) && a[iv][jv] == 0 )
{
Q.push(make_pair(iv, jv));
a[iv][jv] = a[i][j] + 1;
}
}
}
//fout << '\n';
Q.push(make_pair(ij, jj));
while ( !Q.empty() )
{
i = Q.front().first;
j = Q.front().second;
//fout << i << ' ' << j << '\n';
Q.pop();
for ( int d = 0; d < 8; ++d )
{
iv = i + di[d];
jv = j + dj[d];
if ( Inside(iv, jv) && b[iv][jv] == 0 )
{
Q.push(make_pair(iv, jv));
b[iv][jv] = b[i][j] + 1;
}
}
}
/*for ( i = 1; i <= n; i++ )
{
for( j = 1; j <= m; j++ )
fout << a[i][j]<< ' ';
fout << '\n';
}
fout << '\n';
for ( i = 1; i <= n; i++ )
{
for( j = 1; j <= m; j++ )
fout << b[i][j]<< ' ';
fout << '\n';
}
fout << '\n';*/
int k = 0;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
{
if( a[i][j] == b[i][j] && a[i][j] > 0 )
{
v[++k].x = i;
v[k].y = j;
}
}
poz aux;
int min = INF;
//for ( int i = 1; i <= k; i++ )
//fout << v[i].x << ' ' << v[i].y << '\n';
for ( int i = 1; i <= k; i++ )
if ( a[v[1].x][v[1].y] < min )
min = a[v[1].x][v[1].y];
for ( int i = 1; i <= k; i++ )
for( int j = i; j <= k; j++ )
if ( v[i].x > v[j].x && a[v[1].x][v[1].y] == min )
{
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
fout << a[v[1].x][v[1].y] << ' ' << v[1].x << ' ' << v[1].y << '\n';
fin.close();
fout.close();
return 0;
}
bool Inside(int i, int j)
{
return i > 0 && i <= n && j > 0 && j <= m;
}