Pagini recente » Cod sursa (job #3289953) | Cod sursa (job #1601841) | Cod sursa (job #3194850) | Cod sursa (job #1189147) | Cod sursa (job #1133809)
#include <fstream>
#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m;
int M[105][105];
int rx,ry,jx,jy;
queue < pair<int,int> > C;
void BF(int x,int y,int dist[][105])
{
pair <int,int> vec;
C.push(make_pair(x,y));
dist[x][y] = 1;
while(!C.empty())
{
vec = C.front();
if(vec.first>1 && !M[vec.first-1][vec.second])
{
if(!dist[vec.first-1][vec.second])
{
dist[vec.first-1][vec.second] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first-1,vec.second));
}
}
if(!M[vec.first][vec.second+1] && vec.second<m)
{
if(!dist[vec.first][vec.second+1])
{
dist[vec.first][vec.second+1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first,vec.second+1));
}
}
if(!M[vec.first+1][vec.second] && vec.first<n)
{
if(!dist[vec.first+1][vec.second])
{
dist[vec.first+1][vec.second] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first+1,vec.second));
}
}
if(!M[vec.first][vec.second-1] && vec.second>1)
{
if(!dist[vec.first][vec.second-1])
{
dist[vec.first][vec.second-1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first,vec.second-1));
}
}
if(!M[vec.first-1][vec.second-1] && vec.first>1 && vec.second>1)
{
if(!dist[vec.first-1][vec.second-1])
{
dist[vec.first-1][vec.second-1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first-1,vec.second-1));
}
}
if(!M[vec.first+1][vec.second+1] && vec.first<n && vec.second<m)
{
if(!dist[vec.first+1][vec.second+1])
{
dist[vec.first+1][vec.second+1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first+1,vec.second+1));
}
}
if(!M[vec.first+1][vec.second-1] && vec.first<n && vec.second>1)
{
if(!dist[vec.first+1][vec.second-1])
{
dist[vec.first+1][vec.second-1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first+1,vec.second-1));
}
}
if(!M[vec.first-1][vec.second+1] && vec.first>1 && vec.second<m)
{
if(!dist[vec.first-1][vec.second+1])
{
dist[vec.first-1][vec.second+1] = dist[vec.first][vec.second] + 1;
C.push(make_pair(vec.first-1,vec.second+1));
}
}
C.pop();
}
}
int main()
{
int i,j,rendX=0,rendY=0;
int distR[105][105]={0},distJ[105][105]={0};
string space = " ";
fin>>n>>m;
fin.get();
for(i=1;i<=n;++i)
{
string line;
getline(fin,line);
for(j=0;j<m-line.length();++j) line += space;
for(j=0;j<line.length();++j)
{
if(line[j]==' '){M[i][j+1]=0;}
if(line[j]=='X'){M[i][j+1]=-1;}
if(line[j]=='R'){M[i][j+1]=1;rx=i;ry=j+1;}
if(line[j]=='J'){M[i][j+1]=2;jx=i;jy=j+1;}
}
}
BF(rx,ry,distR);
BF(jx,jy,distJ);
int min = m*n;
int retcol = m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(distR[i][j]!=0 && distR[i][j]==distJ[i][j] && distR[i][j]<=min)
min = distR[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(distR[i][j]!=0 && distR[i][j]==min)
if(j<=retcol)
{
rendX = i;
rendY = j;
retcol = j;
}
fout<<min<<" "<<rendX<<" "<<rendY;
return 0;
}