Pagini recente » Cod sursa (job #1910766) | Cod sursa (job #2878596) | Cod sursa (job #1390804) | Cod sursa (job #1057070) | Cod sursa (job #2197508)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const short NMAX = 120;
unsigned short n, m;
queue <pair<unsigned short, unsigned short> > coada;
unsigned short x_R, x_J, y_R, y_J;
bool b[NMAX][NMAX];
unsigned short c[NMAX][NMAX];
char a[NMAX];
unsigned short sol, x_s, y_s;
struct
{
short x, y;
}d[10];
void init()
{
d[1].x = -1, d[1].y = 0;
d[2].x = 0, d[2].y = 1;
d[3].x = 1, d[3].y = 0;
d[4].x = 0, d[4].y = -1;
d[5].x = -1, d[5].y = -1;
d[6].x = -1, d[6].y = 1;
d[7].x = 1, d[7].y = 1;
d[8].x = 1, d[8].y = -1;
}
void Citire()
{
f >> n >> m;
f.get();
for(unsigned short i = 1; i <= n; i++)
{
f.getline(a, NMAX);
for(unsigned short j = 0; j < strlen(a); j++)
if(a[j] == ' ')
b[i][j + 1] = true;
else
{
b[i][j + 1] = false;
if(a[j] == 'R')
x_R = i, y_R = j + 1;
else
if(a[j] == 'J')
x_J = i, y_J = j + 1;
}
if(strlen(a) < m)
for(int j = strlen(a); j <= m; j++)
b[i][j] = true;
}
}
void BFS(unsigned short x, unsigned short y, unsigned short x_stop, unsigned short y_stop)
{
init();
c[x][y] = 1;
coada.push(make_pair(x, y));
bool ok = true;
while(ok)
{
unsigned short x_c = coada.front().first;
unsigned short y_c = coada.front().second;
coada.pop();
for(unsigned short i = 1; i <= 8; i++)
{
unsigned short new_X = x_c + d[i].x;
unsigned short new_Y = y_c + d[i].y;
if(b[new_X][new_Y] && !c[new_X][new_Y])
{
c[new_X][new_Y] = c[x_c][y_c] + 1;
coada.push(make_pair(new_X, new_Y));
}
else
if(new_X == x_stop && new_Y == y_stop)
{
ok = false;
c[x_stop][y_stop] = c[x_c][y_c] + 1;
}
}
}
sol = (c[x_stop][y_stop] + 1) / 2;
while(!coada.empty())
coada.pop();
coada.push(make_pair(x_stop, y_stop));
ok = true;
while(ok)
{
unsigned short x_c = coada.front().first;
unsigned short y_c = coada.front().second;
coada.pop();
for(unsigned short i = 1; i <= 8; i++)
{
unsigned short new_X = x_c + d[i].x;
unsigned short new_Y = y_c + d[i].y;
if(c[new_X][new_Y] == c[x_c][y_c] - 1)
coada.push(make_pair(new_X, new_Y));
if(c[new_X][new_Y] == sol)
{
x_s = new_X;
y_s = new_Y;
ok = false;
}
}
}
}
void Afisare()
{
g << sol << " " << x_s << " " << y_s;
}
int main()
{
Citire();
BFS(x_R, y_R, x_J, y_J);
Afisare();
}