Cod sursa(job #234570)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 21 decembrie 2008 10:59:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>

struct nod{int x,y;nod *urm;};
nod *que,*ultim;

int A[101][101];

void add(int x,int y)
{
nod *urm;
urm = new nod;
urm->x = x;
urm->y = y;
urm->urm = NULL;
if (que==NULL) que=urm,ultim=que;
else ultim->urm = urm,ultim = urm;
}

int main()
{
FILE *in = fopen("rj.in","r");
FILE *out = fopen("rj.out","w");

int x1,y1,x2,y2,i,j,n,m;
char c;
fscanf(in,"%d %d\n",&n,&m);

for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
        {
        fscanf(in,"%c",&c);
        if (c=='X') A[i][j]=-1;
        else
        if (c==' ') A[i][j]=100000;
        else
        if (c=='R') A[i][j]=0,x1=i,y1=j;
        else
        if (c=='J') A[i][j]=0,x2=i,y2=j;
        }
fscanf(in,"\n");
}

nod *scos;
int x,y;

add(x1,y1);
while (que)
{
x=que->x;        printf("%d %d\n",x,y);
y=que->y;
scos = que;
que = que->urm;
delete scos;
if (x>1) if (A[x-1][y]>A[x][y]+1) A[x-1][y]=A[x][y]+1,add(x-1,y);
if (x<m) if (A[x+1][y]>A[x][y]+1) A[x+1][y]=A[x][y]+1,add(x+1,y);
if (y>1) if (A[x][y-1]>A[x][y]+1) A[x][y-1]=A[x][y]+1,add(x,y-1);
if (y<m) if (A[x][y+1]>A[x][y]+1) A[x][y+1]=A[x][y]+1,add(x,y+1);
}

int st=100000,sx,sy;

add(x2,y2);
while (que)
{
x=que->x;
y=que->y;
scos = que;
que = que->urm;
delete scos;
if (x>1) if (A[x-1][y]>A[x][y]+1) A[x-1][y]=A[x][y]+1,add(x-1,y);
         else if (A[x-1][y]==A[x][y]+1) if (st>A[x-1][y]) st=A[x-1][y],sx=x-1,sy=y;
if (x<m) if (A[x+1][y]>A[x][y]+1) A[x+1][y]=A[x][y]+1,add(x+1,y);
         else if (A[x+1][y]==A[x][y]+1) if (st>A[x-1][y]) st=A[x+1][y],sx=x+1,sy=y;
if (y>1) if (A[x][y-1]>A[x][y]+1) A[x][y-1]=A[x][y]+1,add(x,y-1);
         else if (A[x][y-1]==A[x][y]+1) if (st>A[x][y-1]) st=A[x][y-1],sx=x,sy=y-1;
if (y<m) if (A[x][y+1]>A[x][y]+1) A[x][y+1]=A[x][y]+1,add(x,y+1);
         else if (A[x][y+1]==A[x][y]+1) if (st>A[x][y+1]) st=A[x][y+1],sx=x,sy=y+1;
}

//for (i=1;i<=n;i++)
//{
//for (j=1;j<=m;j++)
//fprintf(out,"%d ",A[i][j]);
//fprintf(out,"\n");
//}

fprintf(out,"%d %d %d",st,sx,sy);

}