Pagini recente » Cod sursa (job #1836447) | Cod sursa (job #2324667) | Cod sursa (job #1224169) | Cod sursa (job #2132613) | Cod sursa (job #1130075)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
const int INF = 0x3f3f3f3f;
const int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int m, n, iM, jM;
int a[102][102];
int b[102][102];
char t[102][102], x;
struct Cel{
int i, j;
} R, J;
queue < pair <int, int> > coada;
void Solve()
{
int mi = INF;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{//Cross the matrix
if (a[i][j] == b[i][j] && a[i][j] != 0 && a[i][j] < mi)
iM = i, jM = j, mi = a[i][j];
}
}
fout << mi << " " << iM << " " << jM;
}
bool Ok(int i, int j)
{
if (i < 1 || j < 1 || i > n || j > m) //If pass the margins
return false;
if (t[i][j] == 'X') //If is an obstacle
return false;
return true; //Else is ok
}
void LeeJ()
{
int i, j, iv, jv;
b[J.i][J.j] = 1;
coada.push(make_pair(J.i, J.j)); //Insert the Juliet's coordinates
while ( !coada.empty() ) //If there are elements in queue
{
i = coada.front().first; //Extract first element from queue
j = coada.front().second; //Extract second element from queue
coada.pop(); //Remove the oldest element from queue
for (int d = 0; d < 8; d++)
{
iv = i + di[d]; //Put the coordinates
jv = j + dj[d]; //Put the coordinates
if (Ok(iv, jv) && b[iv][jv] < 1)
{//If it's ok and the new b is 0 :)
b[iv][jv] = b[i][j] + 1;
coada.push(make_pair(iv, jv));
}
}
}
}
void LeeR()
{
int i, j, iv, jv;
a[R.i][R.j] = 1;
coada.push(make_pair(R.i, R.j)); //Insert the Romeo's coordinates
while (!coada.empty()) //If there are elements in queue
{
i = coada.front().first; //Extract first element from queue
j = coada.front().second; //Extract second element from queue
coada.pop(); //Remove the oldest element from queue
for (int d = 0; d < 8; d++)
{
iv = i + di[d]; //Put the coordinates
jv = j + dj[d]; //Put the coordinates
if ( Ok(iv, jv) && a[iv][jv] < 1 )
{//If it's ok and the new a is 0 :)
a[iv][jv] = a[i][j] + 1;
coada.push(make_pair(iv, jv));
}
}
}
}
void Read()
{
fin >> n >> m;
for ( int i = 1; i <= n; i++)
{
for ( int j = 1; j <= m; j++)
{
x = fin.get();
if (x == '\n') x = fin.get();
if (x == 'X' || x == 'R' || x == 'J' || x == ' ')
t[i][j] = x;
if (x == 'R') R.i = i, R.j = j;
if (x == 'J') J.i = i, J.j = j;
}
}
}
int main()
{
Read();
LeeR();
LeeJ();
Solve();
return 0;
}