Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/ricochet1995 | Cod sursa (job #954443) | Monitorul de evaluare | Cod sursa (job #1769439)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char a[102][102];
int rom[102][102];
int jul[102][102];
int dl[10]={ 1,1,1,-1,-1,-1,0, 0};
int dc[10]={-1,0,1,-1, 1, 0,1,-1};
int n,m,rj,ri,jj,ji,iint,jint;
queue< pair <int,int> >q;
void Citire()
{
int i;
fin>>n>>m;
fin.get();
for(i=1;i<=n;i++)
fin.getline((a[i]+1),101);
}
void Bordare()
{
int i,j;
for(i=1;i<=n;i++)
a[i][0]=a[i][m+1]='X';
for(j=1;j<=n;j++)
a[0][j]=a[n+1][j]='X';
}
void preLee()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
jul[i][j]=rom[i][j]=1000000;
if(a[i][j]=='R') {rj=j;ri=i;}
if(a[i][j]=='J') {jj=j;ji=i;}
}
}
void LeeJ()
{
int i,j,k,x,y;
q.push(make_pair(ji,jj));
jul[ji][jj]=1;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(k=0;k<8;k++)
{
x=i+dl[k];
y=j+dc[k];
if(a[x][y]==' '&&jul[x][y]>=jul[i][j]+1)
{
q.push(make_pair(x,y));
jul[x][y]=jul[i][j]+1;
}
}
}
}
void LeeR()
{
int i,j,k,x,y;
q.push(make_pair(ri,rj));
rom[ri][rj]=1;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(k=0;k<8;k++)
{
x=i+dl[k];
y=j+dc[k];
if(a[x][y]==' '&&rom[x][y]>=rom[i][j]+1)
{
q.push(make_pair(x,y));
rom[x][y]=rom[i][j]+1;
}
}
}
}
void CautLoc()
{
int minim=1000000,i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(jul[i][j]==rom[i][j]&&jul[i][j]<=minim)
{
iint=i;
jint=j;
minim=jul[i][j];
}
}
fout<<minim<<" "<<iint<<" "<<jint<<"\n";
}
int main()
{
Citire();
Bordare();
preLee();
LeeJ();
LeeR();
CautLoc();
fin.close();
fout.close();
return 0;
}