Pagini recente » Cod sursa (job #1265790) | Cod sursa (job #3205167) | Cod sursa (job #2674819) | Cod sursa (job #319459) | Cod sursa (job #3129203)
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m,i,j,x1,x2,y3,y2,a,b,x,y,di,dj,min1,rx,ry,jx,jy;
char v[200];
int o[200][200];
int w[200][200],w1[200][200];
int dx[] = {1, 1, -1, -1 ,0, 0 , -1, 1};
int dy[] = {0, 1, 0, -1, 1, -1, 1,-1};
struct coordonate
{
int x,y;
};
coordonate h1,h2;
queue <coordonate> q;
bool interior(int x, int y)
{
return x > 0 && y > 0 && x <=n && y <= m;
}
void LeeR()
{
h1.x=rx;
h1.y=ry;
w[h1.x][h1.y]=1;
q.push(h1);
while(!q.empty())
{
h1=q.front();
q.pop();
for(i=0;i<8;i++)
{
h2.x=dx[i]+h1.x;
h2.y=dy[i]+h1.y;
if(interior(h2.x,h2.y)&&(w[h1.x][h1.y]+1<w[h2.x][h2.y]||w[h2.x][h2.y]==0)&&o[h2.x][h2.y]!=1)
{
w[h2.x][h2.y]=w[h1.x][h1.y]+1;
q.push(h2);
}
}
}
}
void LeeJ()
{
h1.x=jx;
h1.y=jy;
w1[h1.x][h1.y]=1;
q.push(h1);
while(!q.empty())
{
h1=q.front();
q.pop();
for(i=0;i<8;i++)
{
h2.x=h1.x+dx[i];
h2.y=h1.y+dy[i];
if(interior(h2.x,h2.y)&&(w1[h1.x][h1.y]+1<w1[h2.x][h2.y]||w1[h2.x][h2.y]==0)&&o[h2.x][h2.y]!=1)
{
w1[h2.x][h2.y]=w1[h1.x][h1.y]+1;
q.push(h2);
}
}
}
}
int main()
{
f>>n>>m;
f.getline(v,200);
min1=100000;
for(i=1;i<=n;i++)
{
f.getline(v,200);
for(j=0;j<=m;j++)
{
if(v[j]=='X')
o[i][j+1]=1;
if(v[j]=='R')
{
rx=i;
ry=j+1;
}
if(v[j]=='J')
{
jx=i;
jy=j+1;
}
}
}
LeeR();
LeeJ();
/* for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
g<<o[i][j]<<" ";
g<<"\n";
}
g<<"\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
g<<w[i][j]<<" ";
g<<"\n";
}
g<<"\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
g<<w1[i][j]<<" ";
g<<"\n";
}
g<<"\n";
*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i][j]==w1[i][j]&&w[i][j]!=0&&w[i][j]<min1)
{
min1=w[i][j];
di=i;
dj=j;
}
}
g<<min1<<" "<<di<<" "<<dj;
return 0;
}