Pagini recente » Cod sursa (job #2328248) | Cod sursa (job #470869) | Cod sursa (job #1613585) | Cod sursa (job #843391) | Cod sursa (job #323096)
Cod sursa(job #323096)
#include <stdio.h>
#define N 105
#define P 10050
int v[N][N];
const int dlin[]={-1,-1,-1,0,0,1,1,1};
const int dcol[]={-1,0,1,-1,1,-1,0,1};
int n,m,coord1_r,coord2_r,coord1_j,coord2_j,r,t;
struct bfs
{
int a,b,cost;
};
bfs coada[P];
bfs queue[P];
char marc[N][N];
int mat[N][N];
void read()
{
scanf("%d%d\n",&n,&m);
char x;
int lin=1,col=0;
while (scanf("%c",&x)!=EOF)
{
if (x=='\n')
{
lin++;
col=0;
continue;
}
if (x=='R')
{
v[lin][++col]=0;
coord1_r=lin;
coord2_r=col;
continue;
}
if (x=='J')
{
v[lin][++col]=0;
coord1_j=lin;
coord2_j=col;
continue;
}
if (x=='X')
{
v[lin][++col]=1;
continue;
}
if (x==' ')
{
v[lin][++col]=0;
continue;
}
}
}
void bordare()
{
int i,j;
for (i=0; i<=N; i++)
for (j=0; j<=N; j++)
marc[i][j]=0;
for (i=0; i<=n+1; i++)
{
marc[i][0]=1;
marc[i][m+1]=1;
}
for (i=0; i<=m+1; i++)
{
marc[0][i]=1;
marc[n+1][i]=1;
}
}
void bfs_romeo()
{
r=0;
bordare();
coada[++r].a=coord1_r;
coada[r].b=coord2_r;
coada[r].cost=0;
marc[coada[1].a][coada[1].b]=1;
int i,j,ok=1,ant=0,act;
while (ok)
{
ok=0;
act=r;
for (i=ant+1; i<=act; i++)
{
for (j=0; j<8; j++)
{
if (v[coada[i].a+dlin[j]][coada[i].b+dcol[j]]==0 && marc[coada[i].a+dlin[j]][coada[i].b+dcol[j]]==0)
{
coada[++r].a=coada[i].a+dlin[j];
coada[r].b=coada[i].b+dcol[j];
mat[coada[r].a][coada[r].b]=r;
coada[r].cost=coada[i].cost+1;
marc[coada[i].a+dlin[j]][coada[i].b+dcol[j]]=1;
ok=1;
}
}
}
ant=act;
}
}
void bfs_julieta()
{
t=0;
bordare();
queue[++t].a=coord1_j;
queue[t].b=coord2_j;
queue[t].cost=0;
marc[queue[1].a][queue[1].b]=1;
int i,j,ok=1,ant=0,act;
while (ok)
{
ok=0;
act=t;
for (i=ant+1; i<=act; i++)
{
for (j=0; j<8; j++)
{
if (v[queue[i].a+dlin[j]][queue[i].b+dcol[j]]==0 && marc[queue[i].a+dlin[j]][queue[i].b+dcol[j]]==0)
{
queue[++t].a=queue[i].a+dlin[j];
queue[t].b=queue[i].b+dcol[j];
queue[t].cost=queue[i].cost+1;
if (coada[mat[queue[t].a][queue[t].b]].cost==queue[t].cost)
{
printf("%d %d %d\n",queue[t].cost+1,queue[t].a,queue[t].b);
return;
}
marc[queue[i].a+dlin[j]][queue[i].b+dcol[j]]=1;
ok=1;
}
}
}
ant=act;
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
read();
bfs_romeo();
bfs_julieta();
return 0;
}