Pagini recente » Cod sursa (job #614918) | Diferente pentru implica-te/arhiva-educationala intre reviziile 25 si 26 | Cod sursa (job #1376650) | Cod sursa (job #2088656) | Cod sursa (job #583539)
Cod sursa(job #583539)
#include<stdio.h>
#define N 101
const int dx[8]={0,1,0,-1,1,-1,-1,1},dy[8]={1,0,-1,0,1,-1,1,-1};
struct punct {
char lin,col;
};
int m,n,a[N][N],aa2[N][N];
short x1,y1,x2,y2;
char aa[N];
punct q[N*N];
int p=1,u;
void bfs(punct xx) {
punct y; int i;
q[++u]=xx;
a[xx.lin][xx.col]=1;
while(p<=u) {
xx=q[p++];
for(i=0;i<8;++i) {
y.lin=xx.lin+dx[i];
y.col=xx.col+dy[i];
if(a[y.lin][y.col]==0) {
q[++u]=y;
a[y.lin][y.col]=1+a[xx.lin][xx.col];
}
}
}
}
int main() {
int i,j,smin=10000,a1,a2; punct w;
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d\n",&n,&m);
for(i=1;i<=n;++i) {
gets(aa);
for(j=0;j<m;++j) {
if(aa[j]=='X')
a[i][j+1]=-1;
if(aa[j]=='R') {
x1=i; y1=j+1;
}
if(aa[j]=='J') {
x2=i;y2=j+1;
}
}
}
for(i=0;i<=n+1;++i) {
a[i][0]=-1; a[i][m+1]=-1;
}
for(j=0;j<=m+1;++j) {
a[0][j]=-1; a[n+1][j]=-1;
}
w.lin=x1; w.col=y1;
bfs(w);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) {
aa2[i][j]=a[i][j];
if(a[i][j]!=-1)
a[i][j]=0;
}
w.lin=x2; w.col=y2;
u=0; p=1;
bfs(w);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) {
if(a[i][j]==aa2[i][j] && a[i][j]!=0 && a[i][j]!=-1 && a[i][j]<smin) {
smin=a[i][j]; a1=i; a2=j;
}
}
printf("%d %d %d",smin,a1,a2);
return 0;
}