Pagini recente » Cod sursa (job #974730) | Cod sursa (job #2068360) | Cod sursa (job #1274776) | Cod sursa (job #1265280) | Cod sursa (job #2147444)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
#define N 102
short dx[8]={-1,-1,0,1,1,1,0,-1};
short dy[8]={0,1,1,1,0,-1,-1,-1};
int q[N*N][2];
short a[N][N];
short b[N][N];
int main(){
int n,m,i,j,x1,y1,x2,y2;
string s;
in>>n>>m;
getline(in,s);
for(i=1; i<=n; ++i){
getline(in,s);
for(j=0; j<m; ++j){
switch(s[j]){
case 'X': a[i][j+1]=b[i][j+1]=-1; break;
case 'R': x1=i, y1=j+1; a[i][j+1]=1; break;
case 'J': x2=i, y2=j+1; b[i][j+1]=1; break;
}
}
}
for(i=0; i<=n+1; ++i)
a[i][m+1]=a[i][0]=-1;
for(i=0; i<=m+1; ++i)
a[n+1][i]=a[0][i]=-1;
for(i=-1; i<=n+2; ++i)
a[i][m+2]=a[i][-1]=-1;
for(i=-1; i<=m+2; ++i)
a[n+2][i]=a[-1][i]=-1;
int u=0, p=0;
q[++u][0]=x1;
q[u][1]=y1;
int c1,c2,v1,v2;
while(p<=u){
c1=q[++p][0];
c2=q[p][1];
for(i=0; i<8; ++i){
v1=c1+dx[i];
v2=c2+dy[i];
if(a[v1][v2]==0){
a[v1][v2]=a[c1][c2]+1;
q[++u][0]=v1;
q[u][1]=v2;
}
}
}
u=0, p=0;
q[++u][0]=x2;
q[u][1]=y2;
int minn=1000000;
int m1,m2;
for(i=0; i<=n+1; ++i)
b[i][m+1]=b[i][0]=-1;
for(i=0; i<=m+1; ++i)
b[n+1][i]=b[0][i]=-1;
for(i=-1; i<=n+2; ++i)
b[i][m+2]=b[i][-1]=-1;
for(i=-1; i<=m+2; ++i)
b[n+2][i]=b[-1][i]=-1;
while(p<=u){
c1=q[++p][0];
c2=q[p][1];
for(i=0; i<8; ++i){
v1=c1+dx[i];
v2=c2+dy[i];
if(!b[v1][v2]){
b[v1][v2]=b[c1][c2]+1;
q[++u][0]=v1;
q[u][1]=v2;
}
if(b[v1][v2]==a[v1][v2] && b[v1][v2]>0){
if(minn>a[v1][v2])
minn=a[v1][v2], m1=v1, m2=v2;
else if(minn==a[v1][v2]){
if(v1<m1)
minn=a[v1][v2], m1=v1, m2=v2;
else if(v1==m1)
if(v2<m2)
minn=a[v1][v2], m1=v1, m2=v2;
}
}
}
}
out<<minn<<" "<<m1<<" "<<m2;
return 0;
}