Pagini recente » Cod sursa (job #493047) | Cod sursa (job #2956337) | Cod sursa (job #683969) | Cod sursa (job #2562767) | Cod sursa (job #3290367)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
int crx,cry,cjx,cjy;
int minn=20001;
int n,m;
int mij;
int mat[101][101];
char s[101][101];
bool frecv[101][101];
int dif[3]={0,1,-1},tip[3]={2,3,3},comb[3]={1,-1,0};
void lee()
{
queue< pair<int,pair<int, int> > > Q;
Q.push({1,{crx,cry}});
mat[crx][cry]=1;
while(Q.empty()!=1)
{
int xx=Q.front().second.first;
int yy=Q.front().second.second;
int pas=Q.front().first;
if(pas>minn)
return;
if((xx==cjx && yy== cjy)&&((mat[xx][yy]-mat[crx][cry]-1)%2==0))
if(pas<=minn)
minn=pas;
for(int i=0;i<3;i++)
for(int j=0;j<tip[i];j++)
{
int pctx= xx+dif[i];
int pcty= yy+comb[j];
if((pctx>-1 && pctx<n) && (pcty>-1 && pcty<m))
{
if(s[pctx][pcty]!='X')///daca pot sa trec pe aici
{
if(mat[pctx][pcty]==0 || mat[pctx][pcty]>=pas+1)
{
mat[pctx][pcty]=pas+1;
Q.push({pas+1,{pctx,pcty}});
}
}
else ///pe unde nu am voie sa trec
mat[pctx][pcty]=1001;
}
}
Q.pop();
}
}
int rasx=1001,rasy=1001;
void dfs(int xx,int yy)
{
if(frecv[xx][yy])
return;
frecv[xx][yy]=1;
if(mat[xx][yy]==mij)///e la jumatate
{
if(xx<rasx)
{
rasx=xx;
rasy=yy;
}
else if(xx==rasx)
if(yy<rasy)
rasy=yy;
///salvez
}
for(int i=0;i<3;i++)
for(int j=0;j<tip[i];j++)
{
int pctx= xx+dif[i];
int pcty= yy+comb[j];
if((pctx>-1 && pctx<n) && (pcty>-1 && pcty<m))
{
if(mat[pctx][pcty]==mat[xx][yy]-1)
dfs(pctx,pcty);
}
}
}
int main()
{
//int n,m;
//char s[100][101];
cin>>n>>m;
cin.get();
for(int i=0;i<n;i++)
{
cin.getline(s[i],m+1);
int j=0;
while(s[i][j]!='\0')
{
if(s[i][j]=='R')
crx=i,cry=j;
else if(s[i][j]=='J')
cjx=i,cjy=j;
j++;
}
}
///acum lee din R in J
lee();
mij=((mat[cjx][cjy]-mat[crx][cry])/2) + 1;
dfs(cjx,cjy);
/*
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<mat[i][j]<<" ";
cout<<'\n';
}*/
cout<<mij<<" "<<rasx+1<<" "<<rasy+1;
return 0;
}