Pagini recente » Cod sursa (job #724770) | Cod sursa (job #1832275) | Cod sursa (job #801396) | Cod sursa (job #2138035) | Cod sursa (job #1498765)
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <queue>
using namespace std;
class Casuta {
public:
int x, y;
Casuta() { }
Casuta(int x, int y) {
this->x = x, this->y = y;
}
Casuta operator + (const Casuta& other) {
return Casuta(this->x + other.x, this->y + other.y);
}
} dir[] = {
Casuta(-1, 0),
Casuta(+1, 0),
Casuta(0, -1),
Casuta(0, +1),
Casuta(+1, +1),
Casuta(-1, -1),
Casuta(-1, +1),
Casuta(+1, -1)
}, Rs, Js;
queue<Casuta> C;
int R[103][103], J[103][103], N, M;
bool viz[103][103];
void BFS_1() {
for(register int i = 0; i < 103; ++ i)
for(register int j = 0; j < 103; ++ j)
if(R[i][j] != -1)
R[i][j] = -2;
viz[Rs.x][Rs.y] = 1;
R[Rs.x][Rs.y] = 0;
C.push(Rs);
while(!C.empty()) {
Casuta c = C.front();
C.pop();
for(register int k = 0; k < 8; ++ k) {
Casuta v = c + dir[k];
if(1 <= v.x and v.x <= N and 1 <= v.y and v.y <= M)
if(!viz[v.x][v.y] and R[v.x][v.y] != -1) {
viz[v.x][v.y] = 1;
C.push(v);
R[v.x][v.y] = 1 + R[c.x][c.y];
}
}
}
}
void BFS_2() {
memset(viz, 0, sizeof(viz));
while(!C.empty()) C.pop();
for(register int i = 0; i < 103; ++ i)
for(register int j = 0; j < 103; ++ j)
if(J[i][j] != -1)
J[i][j] = -2;
J[Js.x][Js.y] = 0;
C.push(Js);
viz[Js.x][Js.y] = 1;
while(!C.empty()) {
Casuta c = C.front();
C.pop();
for(register int k = 0; k < 8; ++ k) {
Casuta v = c + dir[k];
if(1 <= v.x and v.x <= N and 1 <= v.y and v.y <= M)
if(!viz[v.x][v.y] and J[v.x][v.y] != -1) {
viz[v.x][v.y] = 1;
C.push(v);
J[v.x][v.y] = 1 + J[c.x][c.y];
}
}
}
}
int main(void) {
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d %d\n", &N, &M);
for(register int i = 1; i <= N; ++ i) {
string str;
getline(cin, str);
string :: iterator it = str.begin();
for(register int j = 1; j <= M and it != str.end(); ++ j, ++ it) {
switch(*it) {
case 'R': Rs = Casuta(i, j); break;
case 'J': Js = Casuta(i, j); break;
case 'X': R[i][j] = J[i][j] = -1; break;
}
}
}
BFS_1();
BFS_2();
int minim = 1 << 30;
Casuta Min;
for(register int i = 1; i <= N; ++ i)
for(register int j = 1; j <= M; ++ j)
if(R[i][j] == J[i][j] and R[i][j] != -1 and R[i][j] != -2 and R[i][j] < minim) {
minim = R[i][j];
Min = Casuta(i, j);
fprintf(stderr, "%d %d\n", i, j);
}
printf("%d %d %d\n", ++ minim, Min.x, Min.y);
return 0;
}