Pagini recente » Cod sursa (job #1943274) | Cod sursa (job #939055) | Cod sursa (job #2806644) | Cod sursa (job #3290594) | Cod sursa (job #559146)
Cod sursa(job #559146)
#include<fstream>
#include<queue>
#include<iomanip>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int R[130][130],N,M,J[130][130];
int rx,ry,jx,jy;
struct nod
{ int x,y;
};
queue<nod>q;
nod mp(int x,int y)
{ nod a;
a.x=x , a.y=y;
return a;
}
void bfs()
{ int x,y,xx,yy,i;
q.push(mp(rx,ry));
R[rx][ry]=1;
while(!q.empty())
{ x=q.front().x;
y=q.front().y;
q.pop();
for(i=0;i<8;i++)
{ xx=x+dx[i];
yy=y+dy[i];
if(R[xx][yy]==-1)
continue;
if(R[xx][yy]==0)
R[xx][yy]=R[x][y]+1 , q.push(mp(xx,yy));
}
}
J[jx][jy]=1;
q.push(mp(jx,jy));
while(!q.empty())
{ x=q.front().x;
y=q.front().y;
q.pop();
for(i=0;i<8;i++)
{ xx=x+dx[i];
yy=y+dy[i];
if(J[xx][yy]==-1)
continue;
if(J[xx][yy]==0)
J[xx][yy]=J[x][y]+1 , q.push(mp(xx,yy));
}
}
}
int main()
{ int i,j,xf,yf,min=1000,y;
char x;
in>>N>>M;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
{ in>>noskipws>>x;
if(j==1 && x=='\n')
in>>noskipws>>x;
if(x=='R')
rx=i , ry=j;
if(x=='J')
jx=i , jy=j;
if(x=='X')
R[i][j]=J[i][j]=-1;
}
for(i=0;i<=M+1;i++)
R[N+1][i]=J[N+1][i]=R[0][i]=J[0][i]=-1;
for(j=0;j<=N+1;j++)
R[j][M+1]=J[j][M+1]=R[j][0]=J[j][0]=-1;
bfs();
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
if(R[i][j]==J[i][j] && R[i][j]!=-1 && min>R[i][j] && R[i][j])
{ min=R[i][j];
xf=i;
yf=j;
}
out<<min<<" "<<xf<<" "<<yf;
in.close();
out.close();
return 0;
}