Pagini recente » Cod sursa (job #470961) | Cod sursa (job #851905) | Cod sursa (job #1643649) | Cod sursa (job #1275194) | Cod sursa (job #2447709)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
queue<int>ql,qc;
int n,m,xs,ys,xf,yf,x,y,v[1001][1001];
string c;
pair <int,int>marcat[1001][1001];
int main()
{
cin>>n>>m;
cin.get();
for(int i=1;i<=n;i++){
getline(cin,c);
for(int j=0;j<m;j++){
if(c[j]=='X')
v[i][j+1]=1;
else
v[i][j+1]=0;
if((c[j]=='R'||c[j]=='J') && !xs){
xs=i;
ys=j+1;
}
else
if((c[j]=='R'||c[j]=='J') && xs){
xf=i;
yf=j+1;
}
}
}
int i=xs;
int j=ys;
ql.push(xs);
qc.push(ys);
marcat[xs][ys].first=1;
while(!ql.empty()){
i=ql.front();
j=qc.front();
if(!(v[i][j+1]) && !marcat[i][j+1].first && j+1<=m){
ql.push(i);
qc.push(j+1);
marcat[i][j+1].first=marcat[i][j].first+1;
}
if(!(v[i][j-1]) && !marcat[i][j-1].first && j-1>0){
ql.push(i);
qc.push(j-1);
marcat[i][j-1].first=marcat[i][j].first+1;
}
if(!(v[i+1][j]) && !marcat[i+1][j].first && i+1<=n){
ql.push(i+1);
qc.push(j);
marcat[i+1][j].first=marcat[i][j].first+1;
}
if(!(v[i-1][j]) && !marcat[i-1][j].first && i-1>0){
ql.push(i-1);
qc.push(j);
marcat[i-1][j].first=marcat[i][j].first+1;
}
if(!(v[i-1][j-1]) && !marcat[i-1][j-1].first && i-1>0 && j-1>0){
ql.push(i-1);
qc.push(j-1);
marcat[i-1][j-1].first=marcat[i][j].first+1;
}
if(!(v[i+1][j+1]) && !marcat[i+1][j+1].first && i+1<=n && j+1<=m){
ql.push(i+1);
qc.push(j+1);
marcat[i+1][j+1].first=marcat[i][j].first+1;
}
if(!(v[i+1][j-1]) && !marcat[i+1][j-1].first && i+1<=n && j-1>0){
ql.push(i+1);
qc.push(j-1);
marcat[i+1][j-1].first=marcat[i][j].first+1;
}
if(!(v[i-1][j+1]) && !marcat[i-1][j+1].first && i-1>0 && j+1<=m){
ql.push(i-1);
qc.push(j+1);
marcat[i-1][j+1].first=marcat[i][j].first+1;
}
ql.pop();
qc.pop();
}
i=xf;
j=yf;
ql.push(xf);
qc.push(yf);
marcat[xf][yf].second=1;
while(!ql.empty()){
i=ql.front();
j=qc.front();
if(!(v[i][j+1]) && !marcat[i][j+1].second && j+1<=m){
ql.push(i);
qc.push(j+1);
marcat[i][j+1].second=marcat[i][j].second+1;
}
if(!(v[i][j-1]) && !marcat[i][j-1].second && j-1>0){
ql.push(i);
qc.push(j-1);
marcat[i][j-1].second=marcat[i][j].second+1;
}
if(!(v[i+1][j]) && !marcat[i+1][j].second && i+1<=n){
ql.push(i+1);
qc.push(j);
marcat[i+1][j].second=marcat[i][j].second+1;
}
if(!(v[i-1][j]) && !marcat[i-1][j].second && i-1>0){
ql.push(i-1);
qc.push(j);
marcat[i-1][j].second=marcat[i][j].second+1;
}
if(!(v[i-1][j-1]) && !marcat[i-1][j-1].second && i-1>0 && j-1>0){
ql.push(i-1);
qc.push(j-1);
marcat[i-1][j-1].second=marcat[i][j].second+1;
}
if(!(v[i+1][j+1]) && !marcat[i+1][j+1].second && i+1<=n && j+1<=m){
ql.push(i+1);
qc.push(j+1);
marcat[i+1][j+1].second=marcat[i][j].second+1;
}
if(!(v[i+1][j-1]) && !marcat[i+1][j-1].second && i+1<=n && j-1>0){
ql.push(i+1);
qc.push(j-1);
marcat[i+1][j-1].second=marcat[i][j].second+1;
}
if(!(v[i-1][j+1]) && !marcat[i-1][j+1].second && i-1>0 && j+1<=m){
ql.push(i-1);
qc.push(j+1);
marcat[i-1][j+1].second=marcat[i][j].second+1;
}
ql.pop();
qc.pop();
}
int cost=10e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(marcat[i][j].first==marcat[i][j].second && marcat[i][j].first && marcat[i][j].second<cost){
xs=i;
ys=j;
cost=marcat[i][j].first;
}
}
}
cout<<cost<<" "<<xs<<" "<<ys;
return 0;
}