Pagini recente » Cod sursa (job #296251) | Cod sursa (job #1527140) | Cod sursa (job #1963241) | Cod sursa (job #2226722) | Cod sursa (job #1563596)
#include <fstream>
#include <queue>
using namespace std;
queue < pair<int,int> > q;
int m,n,i,j,ir,jr,jj,ij,x,y,k,mini,z,t,b[105][105],d[105][105];
int v[105][105];
char c;
int main()
{
ifstream f("rj.in");
ofstream g("rj.out");
int dx[]={-1,-1,-1,0,1,1,1,0};
int dy[]={-1,0,1,1,1,0,-1,-1};
f>>n>>m;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
b[i][j]=20000;
d[i][j]=20000;
}
mini=20000;
f.get();
for(i=1; i<=n; i++)
{
f.get(c);
for(j=1; c!='\n'; j++)
{
if(c=='X')
v[i][j]=1;
else
if(c=='R')
{
ir=i;
jr=j;
}
else
if(c=='J')
{
ij=i;
jj=j;
}
f.get(c);
}
}
for(i=0; i<=n+1; i++)
{
v[i][0]=1;
v[i][m+1]=1;
}
for(i=0; i<=m+1; i++)
{
v[0][i]=1;
v[n+1][i]=1;
}
//Primul Lee
b[ir][jr]=0;
q.push(make_pair(ir,jr));
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for (k=0; k<8; k++)
{
x=i+dx[k];
y=j+dy[k];
if(v[x][y]!=1&&b[x][y]>b[i][j]+1)
{
b[x][y]=b[i][j]+1;
q.push(make_pair(x, y));
}
}
}
// al doile Lee
d[ij][jj]=0;
q.push(make_pair(ij,jj));
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for (k=0; k<8; k++)
{
x=i+dx[k];
y=j+dy[k];
if(v[x][y]!=1&&d[x][y]>d[i][j]+1)
{
d[x][y]=d[i][j]+1;
q.push(make_pair(x, y));
}
}
}
//cautare mini
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if(b[i][j]==d[i][j]&&b[i][j]<mini&&v[i][j]==0)
{
mini=d[i][j];
z=i;
t=j;
}
}
g<<mini+1<<" "<<z<<" "<<t<<'\n';
f.close(); g.close();
return 0;
}