Pagini recente » Cod sursa (job #451850) | Cod sursa (job #1522130) | Cod sursa (job #2307352) | Cod sursa (job #2813146) | Cod sursa (job #1322967)
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define Nmax 101
#define inf 32500
FILE *f=fopen ("rj.in","r");
FILE *g=fopen ("rj.out","w");
struct point{
int x, y;
}R, J, aux, auxx, poz;
char v[Nmax][Nmax];
short int cost[2][Nmax][Nmax];
const int d[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
queue < point > Q;
int N, M, sol=inf;
bool inside (int x, int y){
if (x > 0 && y > 0 && x <= N && y <= M) return 1;
return 0;
}
void LEE (point start, int ind){
while (!Q.empty()) Q.pop();
Q.push (start);
cost[ind][start.x][start.y] = 0;
while (!Q.empty()){
aux = Q.front();
Q.pop();
for (int i = 0; i < 8; ++i){
int xx=d[i][0]+aux.x, yy=d[i][1]+aux.y;
if (v[xx][yy] == ' ' && cost[ind][xx][yy] > cost[ind][aux.x][aux.y]+1 && inside(xx,yy)){
auxx.x = xx;
auxx.y = yy;
cost[ind][xx][yy] = cost[ind][aux.x][aux.y]+1;
Q.push (auxx);
}
}
}
}
int main(){
fscanf (f,"%d%d%*c",&N,&M);
for (int i = 1 ; i <= N; ++i){
fgets (v[i]+1,105,f);
if (R.x == 0){
char *p = strchr (v[i]+1,'R');
if (p != NULL){
R.x = i;
R.y = p - v[i];
}
}
if (J.x == 0){
char *p = strchr (v[i]+1,'J');
if (p != NULL){
J.x = i;
J.y = p - v[i];
}
}
}
for (int k = 0; k <= 1; ++k)
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
cost[k][i][j] = inf;
LEE (R,0);
LEE (J,1);
for (int i = 1; i <= N ;++i){
for (int j = 1 ; j <= M ; ++j){
if (cost[0][i][j] == cost[1][i][j] && cost[0][i][j] < sol){
sol = cost[0][i][j];
poz.x = i;
poz.y = j;
}
}
}
fprintf (g,"%d %d %d",sol+1, poz.x, poz.y);
return 0;
}