Pagini recente » Cod sursa (job #1028189) | Cod sursa (job #2279367) | Cod sursa (job #534972) | Cod sursa (job #1639800) | Cod sursa (job #1621870)
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue< pair < int, int > > coada;
int di[8]={0, 0, 1, -1, 1, -1, 1, -1};
int dj[8]={1, -1, 0, 0, 1, 1, -1, -1};
int MapJUL[101][101];
int MapROM[101][101];
int n, m, i, j, startxr, startyr, startxj, startyj;
void read()
{
char s[101];
fin>>n>>m;
fin.getline(s, 101);
for(i=1; i<=n; i++)
{
fin.getline(s, 101);
for(j=0; j<m; j++)
{
if(s[j]=='R') { MapROM[i][j+1]=1; startxr=i; startyr=j+1;}
else if(s[j]=='X') MapROM[i][j+1]=-1;
else if(s[j]==' ') MapROM[i][j+1]=0;
else if(s[j]=='J') { MapROM[i][j+1]=0; startxj=i; startyj=j+1;}
}
}
}
bool ok(int i, int j)
{
if(i<1 || j<1 || i>n|| j>m) return false;
if(MapJUL[i][j]==-1 || MapJUL[i][j]==-1) return false;
return true;
}
bool ok1(int i, int j)
{
if(i<1 || j<1 || i>n || j>m) return false;
if(MapROM[i][j]==-1 || MapROM[i][j]==-1) return false;
return true;
}
void lee_ROM()
{
int i_urmator, j_urmator;
coada.push(make_pair(startxr, startyr));
while(!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for(int directie=0; directie<8; directie++)
{
i_urmator=i+di[directie];
j_urmator=j+dj[directie];
if(ok1(i_urmator, j_urmator) && MapROM[i_urmator][j_urmator]<1)
{
MapROM[i_urmator][j_urmator]=MapROM[i][j]+1;
coada.push(make_pair(i_urmator, j_urmator));
}
}
}
}
void lee_JUL()
{
int i_urm, j_urm;
coada.push(make_pair(startxj, startyj));
while(!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for(int dir=0; dir<8; dir++)
{
i_urm=i+di[dir];
j_urm=j+dj[dir];
if(ok(i_urm, j_urm) && MapJUL[i_urm][j_urm]<1)
{
MapJUL[i_urm][j_urm]=MapJUL[i][j]+1;
coada.push(make_pair(i_urm, j_urm));
}
}
}
}
void dadada()
{
int minim=999999, stopx, stopy;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(MapJUL[i][j]==MapROM[i][j] && MapJUL[i][j]<minim && MapJUL[i][j]>0 && MapROM[i][j]>0)
{
stopx=i;
stopy=j;
minim=MapJUL[i][j];
}
}
}
fout<<MapJUL[stopx][stopy]<<" "<<stopx<<" "<<stopy;
}
int main()
{
read();
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++) MapJUL[i][j]= MapROM[i][j];
MapJUL[startxr][startyr]=0;
MapJUL[startxj][startyj]=1;
}
lee_ROM();
lee_JUL();
dadada();
}