Pagini recente » Cod sursa (job #338208) | Cod sursa (job #2999294) | Cod sursa (job #2723246) | Cod sursa (job #2914659) | Cod sursa (job #553119)
Cod sursa(job #553119)
#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[101][101];
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)
{
for (int j = 1 ; j <= M ; ++j)
{
scanf("%c", &mat[i][j]);
if (mat[i][j] == 'R')
rom = to_single_coord(i,j);
else if (mat[i][j] == 'J')
jul = to_single_coord(i,j);
}
scanf("\n");
}
}
void bfs()
{
freopen("rj.out","w",stdout);
int dist[101][101];
Color color[101][101];
for (int i = 1 ; i <= N ; ++i)
for (int j = 1; j <= M ; ++j)
{
color[i][j] = white;
dist[i][j] = INF;
}
int xc, yc;
to_double_coord(rom, &xc, &yc);
dist[xc][yc] = 0;
color[xc][yc] = gray;
to_double_coord(jul, &xc, &yc);
dist[xc][yc] = 0;
color[xc][yc] = gray;
queue<int> Q;
Q.push(rom);Q.push(jul);
while (!Q.empty())
{
int current_single_coord = Q.front();
Q.pop();
to_double_coord(current_single_coord, &xc, &yc);
if (xc < N - 1)
{
if (color[xc + 1][yc] == white && mat[xc + 1][yc] == ' ')
{
color[xc + 1][yc] = gray;
dist[xc + 1][yc] = dist[xc][yc] + 1;
Q.push(to_single_coord(xc + 1, 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] == ' ')
{
color[cxc][cyc] = gray;
dist[cxc][cyc] = dist[xc][yc] + 1;
Q.push(to_single_coord(cxc, cyc));
}
else if (color[cxc][cyc] != white && dist[cxc][cyc] == dist[xc][yc] + 1)
{
printf("%d %d %d\n",cxc,cyc,dist[cxc][cyc]);
}
}
}
}
color[xc][yc] = black;
}
}