Pagini recente » Cod sursa (job #717613) | Cod sursa (job #3174367) | Cod sursa (job #422647) | Cod sursa (job #759906) | Cod sursa (job #1836355)
#include <cstdio>
using namespace std;
int l1, c1, Min = 2000000000, x1, y1, x2, y2, n, m, t[105][105], t2[105][105];
char s[105][105];
struct coada{
int l, c;
}q[40005], z;
short dx[] = {0, 0, -1, 1};
short dy[] = {-1, 1, 0, 0};
inline void BFS(){
int st = 1, dr = 1;
q[1].l = x1; q[1].c = y1;
t[x1][y1] = 0;
while(st <= dr){
z = q[st++];
for(short k = 0; k < 4 ; ++k){
int x = dx[k] + z.l;
int y = dy[k] + z.c;
if(x >= 1 && y >= 0 && x <= n && y < m && s[x][y] != 'X'){
if(t[x][y] > t[z.l][z.c] + 1){
t[x][y] = t[z.l][z.c] + 1;
q[++dr].l = x; q[dr].c = y;
}
}
}
}
}
inline void BFS2(){
int st = 1, dr = 1;
q[1].l = x2; q[1].c = y2;
t2[x2][y2] = 0;
while(st <= dr){
z = q[st++];
for(short k = 0; k < 4 ; ++k){
int x = dx[k] + z.l;
int y = dy[k] + z.c;
if(x >= 1 && y >= 0 && x <= n && y < m && s[x][y] != 'X'){
if(t2[x][y] > t2[z.l][z.c] + 1){
t2[x][y] = t2[z.l][z.c] + 1;
q[++dr].l = x; q[dr].c = y;
if(t2[x][y] == t[x][y])
if(t2[x][y] < Min)
{l1 = x; Min = t2[x][y]; c1 = y;}
else if(Min == t2[x][y] && y < c1)
l1 = x, c1 = y;
}
}
}
}
}
int main(){
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d%d\n", &n, &m);
for(int i = 1; i <= n ; ++i){
fgets(s[i], 101, stdin);
for(int j = 0; j < m ; ++j){
t[i][j] = 2000000000;
t2[i][j] = 2000000000;
if(s[i][j] == 'R') x1 = i, y1 = j;
else if(s[i][j] == 'J') x2 = i, y2 = j;
}
}
BFS();
BFS2();
printf("%d %d %d", Min, l1, c1 + 1);
return 0;
}