Cod sursa(job #718864)

Utilizator andreii1Ilie Andrei andreii1 Data 21 martie 2012 10:35:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>

using namespace std;

int dl[8]={1,-1,0,0,1,1,-1,-1};
int dc[8]={0,0,-1,1,-1,1,-1,1};
int a[150][150],b[150][150],d[150][150];
int i,n,m,j,x1,y1,x2,y2,p,u,x0,y0,min;
typedef struct {int x;int y;}punct;
char ch;
punct c[151*151],v;
int main()
{
    FILE *f=fopen("rj.in","r");
    FILE *g=fopen("rj.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=0;i<=n+1;i++){a[i][0]=-1;a[i][m+1]=-1;}
    for(i=0;i<=m+1;i++){a[0][i]=-1;a[n+1][i]=-1;}
    fscanf(f,"%c",&ch);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
        fscanf(f,"%c",&ch);
        if(ch=='R'){x1=i;y1=j;}
        if(ch=='J'){x2=i;y2=j;}
        if(ch=='X')a[i][j]=-1;
        }
    fscanf(f,"%c",&ch);
    }
    p=1;u=1;
    c[1].x=x1;
    c[1].y=y1;
    b[x1][y1]=1;
    while(p<=u)
    {
        v=c[p];
        for(i=0;i<=7;i++)
        if(a[dl[i]+v.x][dc[i]+v.y]!=-1&&b[dl[i]+v.x][dc[i]+v.y]==0){b[dl[i]+v.x][dc[i]+v.y]=b[v.x][v.y]+1;u++;c[u].x=dl[i]+v.x;c[u].y=dc[i]+v.y;}
        p++;
    }
    p=1;u=1;
    c[1].x=x2;
    c[1].y=y2;
    d[x2][y2]=1;
    while(p<=u)
    {
        v=c[p];
        for(i=0;i<=7;i++)
        if(a[dl[i]+v.x][dc[i]+v.y]!=-1&&d[dl[i]+v.x][dc[i]+v.y]==0){d[dl[i]+v.x][dc[i]+v.y]=d[v.x][v.y]+1;u++;c[u].x=dl[i]+v.x;c[u].y=dc[i]+v.y;}
        p++;
    }
    min=0x7fffffff;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    if(b[i][j]==d[i][j]&&b[i][j]>0&&b[i][j]<min){x0=i;y0=j;min=b[i][j];}
    fprintf(g,"%d %d %d",x0,y0,min);
    fclose(f);
    fclose(g);
    return 0;

}