Pagini recente » Cod sursa (job #2758101) | Cod sursa (job #2885084) | Cod sursa (job #2964032) | Cod sursa (job #1031120) | Cod sursa (job #1768586)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char a[105][105];
int rom[105][105];
int jul[105][105];
int dl[]={ 1,1,1,-1,-1,-1,0, 0};
int dc[]={-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,j;
fin>>n>>m;
fin.get();
for(i=1;i<=n;i++)
fin.getline((a[i]+1),105);
}
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]=1000000;
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(jj,ji));
jul[jj][ji]=0;
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,x,y;
q.push(make_pair(rj,ri));
rom[rj][ri]=0;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(int 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();
return 0;
}