Pagini recente » Cod sursa (job #939289) | Cod sursa (job #3200081) | Cod sursa (job #730496) | Cod sursa (job #2595567) | Cod sursa (job #2911827)
#include <iostream>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n,m;
struct celula
{
int lin;
int col;
celula()
{
}
celula(int l, int c)
{
lin=l;
col=c;
}
};
queue <struct celula> coada;
int di[8]= {-1, -1, -1, 0, 1, 1, 1, 0};
int dj[8]= {-1, 0, 1, 1, 1, 0, -1, -1};
char s[101];
bool valid(struct celula nod)
{
if(nod.lin>=0 && nod.lin<n && nod.col>=0 && nod.col<m)
return 1;
return 0;
}
void bfs(struct celula start, int d[101][101])
{
int vecin_x;
int vecin_y;
coada.push(start);
d[start.lin][start.col]=0;
struct celula nod;
while(!coada.empty())
{
nod=coada.front();
coada.pop();
for(int k=0; k<8; k++)
{
vecin_x= nod.lin+ di[k];
vecin_y=nod.col+ dj[k];
struct celula vecin= celula(vecin_x, vecin_y);
if(valid(vecin)==1 && d[vecin.lin][vecin.col]!=-2)
{
if(d[vecin.lin][vecin.col]==-1 || d[vecin.lin][vecin.col]>1+ d[nod.lin][nod.col] )
{
d[vecin.lin][vecin.col]=1 + d[nod.lin][nod.col];
coada.push(vecin);
}
}
}
}
}
int main()
{
int nr[101][101];
int nj[101][101];
int i,j;
struct celula start_r, start_j;
in>>n>>m;
in.get();
for( i=0; i<n; i++)
{
in.getline(s,101);
for( j=0; j<=strlen(s)-1; j++)
{
if(s[j]=='R')
{
nr[i][j]=0;
nj[i][j]=-1;
start_r=celula(i,j);
}
else if(s[j]=='J')
{
nj[i][j]=0;
nr[i][j]=-1;
start_j=celula(i,j);
}
else if(s[j]==' ')
{
nj[i][j]=-1;
nr[i][j]=-1;
}
else if(s[j]=='X')
{
nj[i][j]=-2;
nr[i][j]=-2;
}
}
for(int k= strlen(s) ; k<m; k++)
{
nj[i][j]=-1;
nr[i][j]=-1;
}
}
bfs(start_r, nr);
bfs(start_j, nj);
int dmin=-1;
struct celula pos;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
if(nr[i][j]==nj[i][j] && nr[i][j]>=0)
{
if (dmin==-1)
{
dmin=nr[i][j];
pos=celula(i,j);
}
else if(nr[i][j]<dmin)
{
dmin=nr[i][j];
pos=celula(i,j);
}
}
}
out<<dmin+1<<" "<<pos.lin+1<<" "<<pos.col+1;
return 0;
}