Pagini recente » Cod sursa (job #2999165) | Cod sursa (job #408288) | Cod sursa (job #1215305) | Cod sursa (job #290253) | Cod sursa (job #553168)
Cod sursa(job #553168)
#include <cstdio>
#include <queue>
using namespace std;
enum Color {white, black, gray};
const int INF = 9999, dt[3] = {-1, 0, 1};
int M,N,rom,jul;
char mat[151][151];
inline int to_single_coord(int x, int y)
{
int temp = (x << 8) + y;
return temp;
}
inline void to_double_coord(int dc, int *x, int *y)
{
*x = dc >> 8;
*y = dc & 255;
}
inline bool eValid(int x, int y)
{
return (x >= 1 && x <= N) && (y >= 1 && y <= M);
}
void read();
void bfs();
int main()
{
read();
bfs();
return 0;
}
void read()
{
freopen("rj.in", "r", stdin);
scanf("%d %d\n", &N, &M);
for (int i = 1 ; i <= N ; ++i)
gets(mat[i] + 1);
}
void bfs()
{
FILE *f = fopen("rj.out","w");
int dist[2][151][151];
Color color[151][151];
for (int i = 1 ; i <= N ; ++i)
for (int j = 1; j <= M ; ++j)
{
color[i][j] = white;
dist[0][i][j] = dist[1][i][j] = INF;
if (mat[i][j] == 'R')
rom = to_single_coord(i,j);
else if (mat[i][j] == 'J')
jul = to_single_coord(i,j);
}
int xc, yc;
to_double_coord(rom, &xc, &yc);
dist[0][xc][yc] = 0;
color[xc][yc] = gray;
queue<int> Q;
Q.push(rom);
while (!Q.empty())
{
int current_single_coord = Q.front();
Q.pop();
to_double_coord(current_single_coord, &xc, &yc);
for (int i = 0 ; i < 3; ++i)
{
for (int j = 0 ; j < 3; ++j)
{
if (i == 1 && j == 1)
continue;
int cxc = xc + dt[i], cyc = yc + dt[j];
if (eValid(cxc, cyc))
{
if (color[cxc][cyc] == white && mat[cxc][cyc] != 'X')
{
color[cxc][cyc] = gray;
dist[0][cxc][cyc] = dist[0][xc][yc] + 1;
Q.push(to_single_coord(cxc, cyc));
}
}
}
}
color[xc][yc] = black;
}
for (int i = 1 ; i <= N ; ++i)
for (int j = 1; j <= M ; ++j)
color[i][j] = white;
to_double_coord(jul, &xc, &yc);
dist[1][xc][yc] = 0;
color[xc][yc] = gray;
Q.push(jul);
while (!Q.empty())
{
int current_single_coord = Q.front();
Q.pop();
to_double_coord(current_single_coord, &xc, &yc);
for (int i = 0 ; i < 3; ++i)
{
for (int j = 0 ; j < 3; ++j)
{
if (i == 1 && j == 1)
continue;
int cxc = xc + dt[i], cyc = yc + dt[j];
if (eValid(cxc, cyc))
{
if (color[cxc][cyc] == white && mat[cxc][cyc] != 'X')
{
color[cxc][cyc] = gray;
dist[1][cxc][cyc] = dist[1][xc][yc] + 1;
Q.push(to_single_coord(cxc, cyc));
}
}
}
}
color[xc][yc] = black;
}
int mini = 1, minj = 1, mine = INF;
for (int i = 1 ; i <= N ; ++i)
{
for (int j = 1; j <= M ; ++j)
{
if (dist[0][i][j] == dist[1][i][j] && dist[0][i][j] < mine)
{
mine = dist[0][i][j];mini = i;minj = j;
}
}
}
fprintf(f,"%d %d %d\n",mine + 1,mini,minj);
fclose(f);
}