Pagini recente » Cod sursa (job #959512) | Cod sursa (job #1771500) | Istoria paginii runda/runda_ezoterica_3 | Cod sursa (job #1834523) | Cod sursa (job #155017)
Cod sursa(job #155017)
#include <stdio.h>
FILE *fin=fopen("rj.in","r");
FILE *fout=fopen("rj.out","w");
typedef struct {int x,y;} pozitie;
int a[102][102],i,h,m,n,inc,sf,l,c,dr[102][102] ;
pozitie r,j;
char ch;
void drum_r()
{ int ii,jj,tmin,xi,yi;
pozitie C[10002];
for (ii=1;ii<=n;ii++) for (jj=1;jj<=m;jj++) dr[ii][jj]=a[ii][jj];
inc=sf=0; C[0]=r; dr[r.x][r.y]=0;
while (inc<=sf)
{
l=C[inc].x; c=C[inc].y;
if (l>1&&dr[l-1][c]>-1)
if (dr[l-1][c]>dr[l][c]+1) {
dr[l-1][c]=dr[l][c]+1;
C[++sf].x=l-1; C[sf].y=c;
}
if (l<n&&dr[l+1][c]>-1)
if (dr[l+1][c]>dr[l][c]+1) { dr[l+1][c]=dr[l][c]+1;
C[++sf].x=l+1; C[sf].y=c;
}
if (c>1&&dr[l][c-1]>-1)
if (dr[l][c-1]>dr[l][c]+1) { dr[l][c-1]=dr[l][c]+1;
C[++sf].x=l; C[sf].y=c-1;
}
if (c<m&&dr[l][c+1]>-1)
if (dr[l][c+1]>dr[l][c]+1) { dr[l][c+1]=dr[l][c]+1;
C[++sf].x=l; C[sf].y=c+1;
}
if (l>1&&c>1&&dr[l-1][c-1]>-1)
if (dr[l-1][c-1]>dr[l][c]+1){ dr[l-1][c-1]=dr[l][c]+1;
C[++sf].x=l-1; C[sf].y=c-1;
}
if (l>1&&c<m&&dr[l-1][c+1]>-1)
if (dr[l-1][c+1]>dr[l][c]+1){ dr[l-1][c+1]=dr[l][c]+1;
C[++sf].x=l-1; C[sf].y=c+1;
}
if (l<n&&c>1&&dr[l+1][c-1]>-1)
if (dr[l+1][c-1]>dr[l][c]+1){ dr[l+1][c-1]=dr[l][c]+1;
C[++sf].x=l+1; C[sf].y=c-1;
}
if (l<n&&c<m&&dr[l+1][c+1]>-1)
if (dr[l+1][c+1]>dr[l][c]+1){ dr[l+1][c+1]=dr[l][c]+1;
C[++sf].x=l+1; C[sf].y=c+1;
}
inc++;
}
// printf("%d\n",sf);
}
void drum_j()
{pozitie C[10002];
int ii,jj, dj[102][102],tmin,xi,yi;
for (ii=1;ii<=n;ii++) for (jj=1;jj<=m;jj++) dj[ii][jj]=a[ii][jj];
inc=sf=0; C[0]=j; dj[j.x][j.y]=0;
while (inc<=sf)
{
l=C[inc].x; c=C[inc].y;
if (l>1&&dj[l-1][c]>-1)
if (dj[l-1][c]>dj[l][c]+1) {
dj[l-1][c]=dj[l][c]+1;
C[++sf].x=l-1; C[sf].y=c;
}
if (l<n&&dj[l+1][c]>-1)
if (dj[l+1][c]>dj[l][c]+1) { dj[l+1][c]=dj[l][c]+1;
C[++sf].x=l+1; C[sf].y=c;
}
if (c>1&&dr[l][c-1]>-1)
if (dj[l][c-1]>dj[l][c]+1) { dj[l][c-1]=dj[l][c]+1;
C[++sf].x=l; C[sf].y=c-1;
}
if (c<m&&dr[l][c+1]>-1)
if (dj[l][c+1]>dj[l][c]+1) { dj[l][c+1]=dj[l][c]+1;
C[++sf].x=l; C[sf].y=c+1;
}
if (l>1&&c>1&&dj[l-1][c-1]>-1)
if (dj[l-1][c-1]>dj[l][c]+1){ dj[l-1][c-1]=dj[l][c]+1;
C[++sf].x=l-1; C[sf].y=c-1;
}
if (l>1&&c<m&&dj[l-1][c+1]>-1)
if (dj[l-1][c+1]>dj[l][c]+1){ dj[l-1][c+1]=dj[l][c]+1;
C[++sf].x=l-1; C[sf].y=c+1;
}
if (l<n&&c>1&&dj[l+1][c-1]>-1)
if (dj[l+1][c-1]>dj[l][c]+1){ dj[l+1][c-1]=dj[l][c]+1;
C[++sf].x=l+1; C[sf].y=c-1;
}
if (l<n&&c<m&&dj[l+1][c+1]>-1)
if (dj[l+1][c+1]>dj[l][c]+1){ dj[l+1][c+1]=dj[l][c]+1;
C[++sf].x=l+1; C[sf].y=c+1;
}
inc++;
}
tmin=30000; xi=yi=200;
for (ii=1;ii<=n;ii++)
for (jj=1;jj<=m;jj++)
if (dr[ii][jj]==dj[ii][jj])
if (dr[ii][jj]>-1&&tmin>dr[ii][jj]) {tmin=dr[ii][jj]; xi=ii; yi=jj;}
fprintf(fout,"%d %d %d\n",tmin+1,xi,yi);
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
fscanf(fin,"%c",&ch); // citim "\n"
for (i=1;i<=n;i++)
{
for (h=1;h<=m;h++)
{
fscanf(fin,"%c",&ch);
if (ch==' ') a[i][h]=30000; else
if (ch=='X') a[i][h]=-1; else
if (ch=='R') {r.x=i; r.y=h; a[i][h]=30000;} else
if (ch=='J') {j.x=i; j.y=h; a[i][h]=30000;}
}
fscanf(fin,"%c",&ch); //citim '\n'
}
drum_r();
drum_j();
fclose(fin); fclose(fout);
return 0;
}