Pagini recente » Rating Mateescu Vlad (vlad.mateescu) | Cod sursa (job #801069)
Cod sursa(job #801069)
#include <fstream>
#include <algorithm>
using namespace std;
short m,n;
char xum[101];
short R[100][100];
short J[100][100];
short rsx, rsy, jsx, jsy;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
void Read();
void LeeRomeo();
void LeeJulieta();
void Search();
struct deck {
short x;
short y;
};
deck array[10000];
short st, dr;
const short dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
const short dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int main ()
{
Read();
LeeRomeo();
LeeJulieta();
Search();
/*for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
fout << R[i][j] << ' ';
fout << '\n';
}
fout << '\n';
for (int i = 0; i < n; ++i)
{
for (int j = 0 ; j < m; ++j)
fout << J[i][j] << ' ' ;
fout << '\n';
}*/
fin.close ();
fout.close ();
return 0;
}
void Read()
{
fin >> n >> m;
fin.ignore();
//fin.getline (xum, 101);
for (short i = 0; i < n; ++i)
{
fin.getline (xum, 101);
for (int lol = 0; xum[lol] != '\0' ; ++lol)
if (xum[lol] == 'X')
R[i][lol] = J[i][lol] = -1;
else
{
if (xum[lol] == 'R')
{
rsx = i;
rsy = lol;
}
else
if (xum[lol] == 'J')
{
jsx = i;
jsy = lol;
}
R[i][lol] = J[i][lol] = 0;
}
}
}
void LeeRomeo ()
{
short i, j, ii, jj;
R[rsx][rsy] = 1;
st = dr = 0;
array[dr].x = rsx;
array[dr++].y = rsy;
while (st < dr && R[jsx][jsy] == 0)
{
i = array[st].x;
j = array[st].y;
for (short k = 0; k < 8; ++k)
{
ii = i + dx[k];
jj = j + dy[k];
if (ii >= 0 && jj >= 0 && ii < n && jj < m && R[ii][jj] == 0)
{
R[ii][jj] = R[i][j] + 1;
array[dr].x = ii;
array[dr++].y = jj;
}
}
st++;
}
}
void LeeJulieta()
{
short i, j, ii, jj;
J[jsx][jsy] = 1;
st = dr = 0;
array[dr].x = jsx;
array[dr++].y = jsy;
while (st < dr && J[rsx][rsy] == 0)
{
i = array[st].x;
j = array[st].y;
for (short k = 0; k < 8; ++k)
{
ii = i + dx[k]; jj = j + dy[k];
if (ii >= 0 && jj >= 0 && ii < n && jj < m && J[ii][jj] == 0)
{
J[ii][jj] = J[i][j] + 1;
array[dr].x = ii;
array[dr++].y = jj;
}
}
st++;
}
}
void Search ()
{
int fx=100, fy=100;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (R[i][j] == J[i][j] && R[i][j] > 0)
{
if (fx < 100)
{
if (R[i][j] < R[fx][fy])
{
fx = i;
fy = j;
}
else
if (R[i][j] == R[fx][fy])
{
if (i < fx)
{
fx = i;
fy = j;
}
else
if (i == fx && j < fy)
{
fx = i;
fy = j;
}
}
}
else
{
fx = i;
fy = j;
}
}
fout << R[fx++][fy++] << ' ' << fx << ' ' << fy;
}