Pagini recente » Cod sursa (job #853267) | Cod sursa (job #1942651) | Cod sursa (job #1908359) | Cod sursa (job #713637) | Cod sursa (job #850613)
Cod sursa(job #850613)
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int A[200][200];
int B[200][200];
char S[110];
int main ()
{
int N, M;
int i, j;
int Rx, Ry;
int Jx, Jy;
int nowx, nowy;
int vx, vy;
int minn, xmin, ymin;
char c;
queue < pair < int, int > > Q;
pair < int, int > now;
//scanf ("%d %d\n", &N, &M);
in >> N >> M;
//in.ignore ();
for (i = 0; i <= M + 1; i ++){
A[0][i] = -1;
A[N + 1][i] = -1;
B[0][i] = -1;
B[N + 1][i] = -1;
}
for (i = 0; i <= N + 1; i ++){
A[i][0] = -1;
A[i][M + 1] = -1;
B[i][0] = -1;
B[i][M + 1] = -1;
}
/*for (i = 0; i <= N + 1; i ++){
for (j = 0; j <= M + 1; j ++)
cout << A[i][j] << " ";
cout << "\n";
}*/
for (i = 1; i <= N; i ++){
in.get ();
in.get (S, 105);
//in.getline (S, 105);
for (j = 0; j < M; j ++){
c = S[j];
if (c == 'R'){
A[i][j + 1] = 1;
B[i][j + 1] = -1;
Rx = i;
Ry = j + 1;
}
if (c == 'J'){
B[i][j + 1] = 1;
A[i][j + 1] = -1;
Jx = i;
Jy = j + 1;
}
if (c == 'X'){
A[i][j + 1] = -1;
B[i][j + 1] = -1;
}
}
}
/*for (i = 0; i <= N + 1; i ++){
for (j = 0; j <= M + 1; j ++)
cout << A[i][j] << " ";
cout << "\n";
}*/
//cout << "\n" << Rx << " " << Ry << "\n" << Jx << " " << Jy;
Q.push (make_pair (Rx, Ry));
while (!Q.empty ()){
now = Q.front ();
Q.pop ();
nowx = now.first;
nowy = now.second;
for (i = 0; i < 8; i ++){
vx = nowx + dx[i];
vy = nowy + dy[i];
if (A[vx][vy] == -1)
continue;
if ((!A[vx][vy]) || (A[vx][vy] > A[nowx][nowy] + 1)){
A[vx][vy] = A[nowx][nowy] + 1;
Q.push (make_pair (vx, vy));
}
}
}
Q.push (make_pair (Jx, Jy));
while (!Q.empty ()){
now = Q.front ();
Q.pop ();
nowx = now.first;
nowy = now.second;
for (i = 0; i < 8; i ++){
vx = nowx + dx[i];
vy = nowy + dy[i];
if (B[vx][vy] == -1)
continue;
if ((!B[vx][vy]) || (B[vx][vy] > B[nowx][nowy] + 1)){
B[vx][vy] = B[nowx][nowy] + 1;
Q.push (make_pair (vx, vy));
}
/*if (A[vx][vy] == B[vx][vy]){
out << A[vx][vy] << " " << vx << " " << vy;
return 0;
}*/
}
}
minn = (1 << 30);
for (i = 1; i <= N; i ++)
for (j = 1; j <= M; j ++)
if (A[i][j] && A[i][j] != -1 && A[i][j] == B[i][j] && A[i][j] < minn){
//out << A[i][j] << " " << i << " " << j;
minn = A[i][j];
xmin = i;
ymin = j;
}
out << minn << " " << xmin << " " << ymin;
return 0;
}