Pagini recente » Cod sursa (job #174561) | Cod sursa (job #1722862) | Cod sursa (job #1735752) | Cod sursa (job #2869319) | Cod sursa (job #2197494)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int NMAX = 150;
int n, m;
queue <pair<int, int> > coada;
int x_R, x_J, y_R, y_J;
char a[NMAX][NMAX];
bool b[NMAX][NMAX];
int c[NMAX][NMAX];
int sol, x_s, y_s;
struct
{
int x, y;
}d[6];
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;
}
void Citire()
{
f >> n >> m;
f.get();
for(int i = 1; i <= n; i++)
{
f.getline(a[i], NMAX);
for(int j = strlen(a[i]); j < m; j++)
a[i][j] = ' ';
a[i][m] = '\0';
for(int j = 0; j < m; j++)
if(a[i][j] == ' ')
b[i][j + 1] = true;
else
{
b[i][j + 1] = false;
if(a[i][j] == 'R')
x_R = i, y_R = j + 1;
else
if(a[i][j] == 'J')
x_J = i, y_J = j + 1;
}
}
}
void BFS(int x, int y, int x_stop, int y_stop)
{
init();
c[x][y] = 1;
coada.push(make_pair(x, y));
bool ok = true;
while(ok)
{
int x_c = coada.front().first;
int y_c = coada.front().second;
coada.pop();
for(int i = 1; i <= 4; i++)
{
int new_X = x_c + d[i].x;
int 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)
{
int x_c = coada.front().first;
int y_c = coada.front().second;
coada.pop();
for(int i = 1; i <= 4; i++)
{
int new_X = x_c + d[i].x;
int 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 + 1)
{
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();
}