Cod sursa(job #1518176)

Utilizator andreeacozma95Cozma Andreea andreeacozma95 Data 5 noiembrie 2015 17:57:53
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct
{
    int l;
    int c;
}coada;

int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int n,m;
short a[102][102];
int rm[100][100],jm[100][100];
coada c[20050];
int start=0,stop=0;
int ir,jr,ij,jj;

void citire()
{
    int i,j;
    char c;
    FILE *f=fopen ("rj.in","r");
    fscanf(f,"%d%d",&n,&m);

    for(i=0;i<=n+1;i++) //bordez cu -1
    {
        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;
    }

    for(i=1;i<=n;i++)
    {
        fscanf(f,"%c",&c);
        for(j=1;j<=m;j++)
        {
            fscanf(f,"%c",&c);
            a[i][j]=(c=='X')?1:0;
            rm[i][j]=0;
            jm[i][j]=0;

            if(c=='R')
                ir=i, jr=j;
            if(c=='J')
                ij=i, jj=j;
        }
    }
}

void push(int i,int j)
{
    c[stop].l=i;
    c[stop].c=j;
    stop++;
}

coada pop()
{
    return c[start++];
}

void lee(int h[100][100])
{
    coada punct;
    while(start!=stop)
    {
       punct=pop();
       int k;
        for(k=0;k<8;k++)
           // if(punct.l+dx[k]>=1 && punct.l+dx[k]<=n && punct.c+dy[k]>=1 && punct.c+dy[k]<=m)
                if(a[punct.l+dx[k]][punct.c+dy[k]]==0 && (h[punct.l+dx[k]][punct.c+dy[k]]==0 || h[punct.l+dx[k]][punct.c+dy[k]]>h[punct.l][punct.c]+1))
                {
                    h[punct.l+dx[k]][punct.c+dy[k]]=h[punct.l][punct.c]+1;
                    push(punct.l+dx[k],punct.c+dy[k]);
                }
    }
}

int max(int a,int b)
{
    return (a>b)? a:b;
}

int main()
{
    int i,j,min=2000000,imin=0,jmin=0,min_pas=90000;
    FILE *g=fopen("rj.out","w");

    citire();

    a[ir][jr]=1;
    a[ij][jj]=1;

    push(ir,jr);
    lee(rm);
    push(ij,jj);
    lee(jm);

     for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
                if(abs(rm[i][j]-jm[i][j])<min && max(rm[i][j],jm[i][j])<=min_pas && rm[i][j]!=0 && jm[i][j]!=0)
                {
                    min=abs(rm[i][j]-jm[i][j]);
                    imin=i;
                    jmin=j;
                    min_pas=max(rm[i][j],jm[i][j]);
                }
                else
                {
                    if(abs(rm[i][j]-jm[i][j])==min && max(rm[i][j],jm[i][j])<=min_pas && rm[i][j]!=0 && jm[i][j]!=0 )
                        if(i<imin)
                        {
                            imin=i;
                            jmin=j;
                            min_pas=max(rm[i][j],jm[i][j]);
                        }
                        else
                            if(i==imin && j<jmin)
                            {
                                imin=i;
                                jmin=j;
                                min_pas=max(rm[i][j],jm[i][j]);
                            }
                }

    fprintf(g,"%d %d %d\n",rm[imin][jmin],imin,jmin);
    return 0;
}