Pagini recente » Cod sursa (job #1672270) | Cod sursa (job #1253139) | Cod sursa (job #1675187) | Cod sursa (job #1084217) | Cod sursa (job #1338360)
#include <fstream>
#include <cstring>
#include <queue>
#include <utility>
#define NMAX 100
using namespace std;
char mat[NMAX+5][NMAX+5];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
int dist1[NMAX+5][NMAX+5];
int dist2[NMAX+5][NMAX+5];
queue<pair<int,int> > coada;
int main()
{
ifstream cin("rj.in");
ofstream cout("rj.out");
int n=1,m=1;
cin>>n>>m;
int i;
for(i=1;i<=n;i++) {
cin.get();
cin.get(mat[i]+1,NMAX+5);
}
//BFS-R
int j,k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(mat[i][j]=='R') {
coada.push(make_pair(i,j));
dist1[i][j]=1;
}
pair<int,int> y;
int nx,ny;
while(!coada.empty()) {
y=coada.front();
coada.pop();
for(k=0;k<8;k++) {
nx=y.first+dx[k];
ny=y.second+dy[k];
if(nx>=1 && ny>=1 && nx<=n && ny<=m && !dist1[nx][ny] && mat[nx][ny]!='X') {
dist1[nx][ny]=1+dist1[y.first][y.second];
coada.push(make_pair(nx,ny));
}
}
}
//BFS-J
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(mat[i][j]=='J') {
coada.push(make_pair(i,j));
dist2[i][j]=1;
}
while(!coada.empty()) {
y=coada.front();
coada.pop();
for(k=0;k<8;k++) {
nx=y.first+dx[k];
ny=y.second+dy[k];
if(nx>=1 && ny>=1 && nx<=n && ny<=m && !dist2[nx][ny] && mat[nx][ny]!='X') {
dist2[nx][ny]=1+dist2[y.first][y.second];
coada.push(make_pair(nx,ny));
}
}
}
int t=2000000005,l,c;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(dist1[i][j] && dist1[i][j]==dist2[i][j])
if(dist1[i][j]<t) {
t=dist1[i][j];
l=i;
c=j;
}
cout<<t<<' '<<l<<' '<<c<<'\n';
cin.close();
cout.close();
return 0;
}