Pagini recente » Cod sursa (job #1514578) | Cod sursa (job #1015850) | Cod sursa (job #1617346) | Cod sursa (job #1791958) | Cod sursa (job #454646)
Cod sursa(job #454646)
#include <stdio.h>
#include <vector>
using namespace std;
const char InFile[]="rj.in";
const char OutFile[]="rj.out";
const int MaxN=205;
FILE *f;
int r[MaxN][MaxN];
int j[MaxN][MaxN];
int n,m,rx,ry,jx,jy,minx,miny,mins=1<<30;
char c;
struct pos{int x,y;};
void lee_r()
{
for(int i=0;i<=n+1;++i)
{
r[i][0]=-1;
r[i][m+1]=-1;
}
for(int i=0;i<=m+1;++i)
{
r[0][i]=-1;
r[n+1][i]=-1;
}
vector<pos> v1,v2;
pos t;
t.x=rx;
t.y=ry;
v1.push_back(t);
int step=1;
r[rx][ry]=step;
while(v1.size())
{
++step;
for(int i=0;i<(int)v1.size();++i)
{
if(r[v1[i].x+1][v1[i].y]==0)
{
r[v1[i].x+1][v1[i].y]=step;
t.x=v1[i].x+1;
t.y=v1[i].y;
v2.push_back(t);
}
if(r[v1[i].x-1][v1[i].y]==0)
{
r[v1[i].x-1][v1[i].y]=step;
t.x=v1[i].x-1;
t.y=v1[i].y;
v2.push_back(t);
}
if(r[v1[i].x][v1[i].y+1]==0)
{
r[v1[i].x][v1[i].y+1]=step;
t.x=v1[i].x;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(r[v1[i].x][v1[i].y-1]==0)
{
r[v1[i].x][v1[i].y-1]=step;
t.x=v1[i].x;
t.y=v1[i].y-1;
v2.push_back(t);
}
if(r[v1[i].x+1][v1[i].y+1]==0)
{
r[v1[i].x+1][v1[i].y+1]=step;
t.x=v1[i].x+1;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(r[v1[i].x+1][v1[i].y-1]==0)
{
r[v1[i].x+1][v1[i].y-1]=step;
t.x=v1[i].x+1;
t.y=v1[i].y-1;
v2.push_back(t);
}
if(r[v1[i].x-1][v1[i].y+1]==0)
{
r[v1[i].x-1][v1[i].y+1]=step;
t.x=v1[i].x-1;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(r[v1[i].x-1][v1[i].y-1]==0)
{
r[v1[i].x-1][v1[i].y-1]=step;
t.x=v1[i].x-1;
t.y=v1[i].y-1;
v2.push_back(t);
}
}
v1=v2;
v2.resize(0);
}
}
void lee_j()
{
for(int i=0;i<=n+1;++i)
{
j[i][0]=-1;
j[i][m+1]=-1;
}
for(int i=0;i<=m+1;++i)
{
j[0][i]=-1;
j[n+1][i]=-1;
}
vector<pos> v1,v2;
pos t;
t.x=jx;
t.y=jy;
v1.push_back(t);
int step=1;
j[jx][jy]=step;
while(v1.size())
{
++step;
for(int i=0;i<(int)v1.size();++i)
{
if(j[v1[i].x+1][v1[i].y]==0)
{
j[v1[i].x+1][v1[i].y]=step;
t.x=v1[i].x+1;
t.y=v1[i].y;
v2.push_back(t);
}
if(j[v1[i].x-1][v1[i].y]==0)
{
j[v1[i].x-1][v1[i].y]=step;
t.x=v1[i].x-1;
t.y=v1[i].y;
v2.push_back(t);
}
if(j[v1[i].x][v1[i].y+1]==0)
{
j[v1[i].x][v1[i].y+1]=step;
t.x=v1[i].x;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(j[v1[i].x][v1[i].y-1]==0)
{
j[v1[i].x][v1[i].y-1]=step;
t.x=v1[i].x;
t.y=v1[i].y-1;
v2.push_back(t);
}
if(j[v1[i].x+1][v1[i].y+1]==0)
{
j[v1[i].x+1][v1[i].y+1]=step;
t.x=v1[i].x+1;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(j[v1[i].x+1][v1[i].y-1]==0)
{
j[v1[i].x+1][v1[i].y-1]=step;
t.x=v1[i].x+1;
t.y=v1[i].y-1;
v2.push_back(t);
}
if(j[v1[i].x-1][v1[i].y+1]==0)
{
j[v1[i].x-1][v1[i].y+1]=step;
t.x=v1[i].x-1;
t.y=v1[i].y+1;
v2.push_back(t);
}
if(j[v1[i].x-1][v1[i].y-1]==0)
{
j[v1[i].x-1][v1[i].y-1]=step;
t.x=v1[i].x-1;
t.y=v1[i].y-1;
v2.push_back(t);
}
}
v1=v2;
v2.resize(0);
}
}
int main()
{
f=fopen(InFile,"r");
fscanf(f,"%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
fscanf(f,"%c",&c);
for(int k=1;k<=m;++k)
{
fscanf(f,"%c",&c);
if(c=='X')
{
r[i][k]=-1;
j[i][k]=-1;
}
else if(c=='R')
{
rx=i;
ry=k;
}
else if(c=='J')
{
jx=i;
jy=k;
}
}
}
fclose(f);
lee_r();
lee_j();
for(int i=1;i<=n;++i)
{
for(int k=1;k<=m;++k)
{
if(r[i][k]==j[i][k] && r[i][k]>0 && r[i][k]<mins)
{
mins=r[i][k];
minx=i;
miny=k;
}
}
}
f=fopen(OutFile,"w");
fprintf(f,"%d %d %d",mins,minx,miny);
fclose(f);
return 0;
}