Pagini recente » Cod sursa (job #700122) | Cod sursa (job #545661) | Cod sursa (job #3136634) | Cod sursa (job #986453) | Cod sursa (job #678610)
Cod sursa(job #678610)
#include <fstream>
#include <deque>
#define M 102
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int dx[8]= {1,-1,1,0,-1,-1,0,1};
int dy[8]= {0,0,1,-1,-1,1,1,-1};
struct poz
{
int l,c;
};
poz aux;
deque<poz> D;
int i,j,n,m,a[M][M],len,b[M][M],bb[M][M],ir,jr,ij,jj,d,mini,soli,solj;
string s;
void pushr(int l, int c, int v)
{
if(l<1 || l>n) return;
if(c<1 || c>m) return;
if(a[l][c]<0) return;
if(b[l][c]>=0 && v>=b[l][c]) return;
b[l][c]=v;
aux.l=l;
aux.c=c;
D.push_back(aux);
}
void pushj(int l, int c, int v)
{
if(l<1 || l>n) return;
if(c<1 || c>m) return;
if(a[l][c]<0) return;
if(bb[l][c]>=0 && v>=bb[l][c]) return;
bb[l][c]=v;
aux.l=l;
aux.c=c;
D.push_back(aux);
}
int main()
{
f>>n>>m;
f.get();
for(i=1; i<=n; i++)
{
getline(f,s);
len=s.size();
for(j=0; j<len; j++)
{
if(s[j]=='X')a[i][j+1]=-1;
if(s[j]==' ')a[i][j+1]=0;
if(s[j]=='R') ir=i,jr=j+1;
if(s[j]=='J') ij=i,jj=j+1;
}
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++) b[i][j]=-1;
b[ir][jr]=1;
aux.l=ir;
aux.c=jr;
D.push_back(aux);
while(!D.empty())
{
aux=D.front();
D.pop_front();
i=aux.l;
j=aux.c;
for(d=0; d<8; d++)
pushr(i+dx[d],j+dy[d],b[i][j]+1);
}
D.clear();
for(i=1; i<=n; i++)
for(j=1; j<=m; j++) bb[i][j]=-1;
bb[ij][jj]=1;
aux.l=ij;
aux.c=jj;
D.push_back(aux);
while(!D.empty())
{
aux=D.front();
D.pop_front();
i=aux.l;
j=aux.c;
for(d=0; d<8; d++)
pushj(i+dx[d],j+dy[d],bb[i][j]+1);
}
mini=1000000;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
if(b[i][j]!=-1 && b[i][j]!=0 && b[i][j]==bb[i][j] && b[i][j]<mini)
{
mini=b[i][j];
soli=i;
solj=j;
}
g<<mini<<' '<<soli<<' '<<solj<<' '<<'\n';
return 0;
}