Pagini recente » Monitorul de evaluare | Cod sursa (job #1208071) | Cod sursa (job #1759086) | Cod sursa (job #2912000) | Cod sursa (job #394474)
Cod sursa(job #394474)
#include <fstream>
#include <iostream>
#define INF 9999
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int a[101][101],dr[101][101],dj[101][101];
int Qr[11000][2],lir,lsr,Qj[11000][2],lij,lsj;
int dir[]={0,0,1,1,1,-1,-1,-1};
int dij[]={1,-1,0,1,-1,0,1,-1};
bool marc[101][101],marc2[101][101];
int main ()
{
int i,n,m,j,auxi,auxj,jpj,jpi,rpj,rpi,njr,nij,njj,nir;
string sirr;
char sir;
in>>n>>m;
getline(in,sirr);
for(i=1;i<=n;i++)
{
//getline(in,sir);
for(j=0;j<m;j++)
{
in.get(sir);
if(sir=='\n')j--;
else
if(sir==' '||sir=='R'||sir=='J')
{
a[i][j+1]=1;
if(sir=='R')
{
rpi=i;
rpj=j+1;
}
else
if(sir=='J')
{
jpi=i;
jpj=j+1;
}
}
dr[i][j+1]=INF;
dj[i][j+1]=INF;
}
}
Qr[0][0]=rpi;
Qr[0][1]=rpj;
lsr++;
dr[rpi][rpj]=1;
Qj[0][0]=jpi;
Qj[0][1]=jpj;
dj[jpi][jpj]=1;
lsj++;
while(lir<lsr&&lij<lsj)
{
nir=Qr[lir][0];
njr=Qr[lir][1];
nij=Qj[lij][0];
njj=Qj[lij][1];
lir++;
lij++;
marc[nir][njr]=1;
if(a[nir][njr]==1)
for(i=0;i<8;i++)
{
auxi=nir+dir[i];
auxj=njr+dij[i];
if(marc[auxi][auxj]==0&&dr[auxi][auxj]>dr[nir][njr]+1&&a[auxi][auxj]==1)
{
dr[auxi][auxj]=dr[nir][njr]+1;
Qr[lsr][0]=auxi;
Qr[lsr][1]=auxj;
lsr++;
}
}
marc2[nij][njj]=1;
if(a[nij][njj]==1)
for(i=0;i<8;i++)
{
auxi=nij+dij[i];
auxj=njj+dir[i];
if(marc2[auxi][auxj]==0&&dj[auxi][auxj]>dj[nij][njj]+1&&a[auxi][auxj]==1)
{
dj[auxi][auxj]=dj[nij][njj]+1;
Qj[lsj][0]=auxi;
Qj[lsj][1]=auxj;
lsj++;
}
}
}
int min=9999;
int pozi=0,pozj=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dr[i][j]==dj[i][j]&&dr[i][j]<min)
{
pozi=i;
pozj=j;
min=dr[i][j];
}
out<<min<<' '<<pozi<<' '<<pozj;
/*
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if(dr[i][j]==INF)
out<<"- ";
else
out<<dr[i][j]<<" ";
out<<'\n';}
out<<"\n\n\n";
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if(dj[i][j]==INF)
out<<"- ";
else
out<<dj[i][j]<<" ";
out<<'\n';}
*/
return 0;
}