Pagini recente » Cod sursa (job #320773) | Cod sursa (job #536762) | Cod sursa (job #3038353) | Cod sursa (job #1013171) | Cod sursa (job #582125)
Cod sursa(job #582125)
#include<stdio.h>
int a[101][101],b[101][101];
int n,m,min=10001,maxi,maxj;
struct punct{int lin,col;};
const int dlin[]={-1,-1,-1, 0, 1, 1, 1, 0};
const int dcol[]={-1, 0, 1, 1, 1, 0,-1,-1};
void bfs1(punct x0)
{
punct q[100001],x,y;
int p=1,u=0;
q[++u]=x0;
a[x0.lin][x0.col]=1;
while(p<=u)
{
x=q[p++];
for(int i=0;i<8;i++)
{
y.lin=x.lin+dlin[i];
y.col=x.col+dcol[i];
if(a[y.lin][y.col]==0)
{
a[y.lin][y.col]=a[x.lin][x.col]+1;
q[++u]=y;
}
}
}
}
void bfs2(punct x0)
{
punct q[100001],x,y;
int p=1,u=0;
q[++u]=x0;
b[x0.lin][x0.col]=1;
while(p<=u)
{
x=q[p++];
for(int i=0;i<8;i++)
{
y.lin=x.lin+dlin[i];
y.col=x.col+dcol[i];
if(b[y.lin][y.col]==0)
{
b[y.lin][y.col]=b[x.lin][x.col]+1;
q[++u]=y;
}
}
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d\n",&n,&m);
int i,j;
punct x1,x2;
char c;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%c",&a[i][j]);
if(a[i][j]==' ')
a[i][j]=0;
if(a[i][j]=='X')
a[i][j]=-1;
if(a[i][j]=='R')
{
x1.lin=i;x1.col=j;
a[i][j]=-1;
}
if(a[i][j]=='J')
{
x2.lin=i;x2.col=j;
a[i][j]=-1;
}
}
scanf("%c",&c);
}
for(i=0;i<=n+1;i++)
a[i][0]=a[i][m+1]=-1;
for(i=0;i<=m+1;i++)
a[0][i]=a[n+1][i]=-1;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
b[i][j]=a[i][j];
bfs1(x1);
bfs2(x2);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
//printf("%d ",a[i][j]);
if(b[i][j]==a[i][j]&&a[i][j]!=-1&&a[i][j]!=0&&a[i][j]<min)
{
min=a[i][j];
maxi=i;
maxj=j;
}
}
//printf("\n");
}
/*printf("\n\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}
*/
printf("%d %d %d",min,maxi,maxj);
return 0;
}