Pagini recente » Cod sursa (job #678322) | Cod sursa (job #2343077) | Cod sursa (job #3182439) | Cod sursa (job #623143) | Cod sursa (job #3149877)
#include <bits/stdc++.h>
using namespace std;
bool v[102][102];
int inf=1e9;
int dist[102][102];
int dist2[102][102];
int diri[8]={1,0,-1,0,1,-1,-1,1};
int dirj[8]={0,1,0,-1,1,-1,1,-1};
int main()
{
ifstream cin("rj.in");
ofstream cout("rj.out");
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dist[i][j]=inf;
dist2[i][j]=inf;
}
}
for(int i=1;i<=n;i++)
{
v[i][0]=1;
v[i][m+1]=1;
}
for(int j=2;j<=m;j++)
{
v[n+1][j]=1;
v[0][j]=1;
}
v[n+1][m+1]=1;
v[0][m+1]=1;
v[n+1][0]=1;
v[0][0]=1;
cin.get();
int inc1,inc2,en1,en2;
for(int i=1;i<=n;i++)
{char c;
for(int j=1;j<=m;j++)
{
c=cin.get();
if(c=='X')
{
v[i][j]=1;
}
if(c=='R')
{
inc1=i;
inc2=j;
// cout<<i<<" "<<j<<'\n';
}
if(c=='J')
{
en1=i;
en2=j;
}
}
if(c!='\n')
cin.get();
}
//cin>>inc1>>inc2>>en1>>en2;
queue<pair<int,int>>q;
q.push({inc1,inc2});
dist[inc1][inc2]=1;
while(!q.empty())
{
int a=q.front().first;
int b=q.front().second;
q.pop();
//v[a][b]=1;
for(int i=0;i<8;i++)
{
if(v[a+diri[i]][b+dirj[i]]==0 && dist[a][b]+1<dist[a+diri[i]][b+dirj[i]])
{
dist[a+diri[i]][b+dirj[i]]=dist[a][b]+1;
q.push({a+diri[i],b+dirj[i]});
}
}
} ////////////////////////////////////////////////////////////////////////////////////////////////
q.push({en1,en2});
dist2[en1][en2]=1;
while(!q.empty())
{
int a=q.front().first;
int b=q.front().second;
q.pop();
//v[a][b]=1;
for(int i=0;i<8;i++)
{
if(v[a+diri[i]][b+dirj[i]]==0 && dist2[a][b]+1<dist2[a+diri[i]][b+dirj[i]])
{
dist2[a+diri[i]][b+dirj[i]]=dist2[a][b]+1;
q.push({a+diri[i],b+dirj[i]});
}
}
}
int ans=2e9,c1,c2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(dist[i][j]==dist2[i][j] && dist[i][j]!=0)
{
if(ans>dist[i][j])
{
ans=dist[i][j];
c1=i;
c2=j;
}
}
//cout<<v[i][j]<<" ";
}
// cout<<'\n';
}
//cout<<'\n';
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(dist[i][j]==dist2[i][j] && dist[i][j]!=0)
{
if(ans>dist[i][j])
{
ans=dist[i][j];
c1=i;
c2=j;
}
}
// cout<<dist2[i][j]<<" ";
}
//cout<<'\n';
}
cout<<ans<<" "<<c1<<" "<<c2;
return 0;
}