Cod sursa(job #1401297)

Utilizator felixiPuscasu Felix felixi Data 25 martie 2015 19:26:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 10.04 kb
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct str
{
    int x,y;
} r,ju;
void citire(int &n,int &m,int **&a,char *fis)
{
    FILE *f;
    f=fopen(fis,"r");
    fscanf(f,"%d%d",&n,&m);
    int i,j;
    a=new int *[n+1];
    for(i=0; i<=n; i++)
    {
        a[i]=new int[m+1];
        a[i][0]=0;
    }
    char aa[n+1][m+1];
    for(i=0; i<=n; i++) fgets(aa[i],m+2,f);

    int k=1;
    for(i=1; i<=n; i++)
        for(j=0; j<m; j++)
            switch(aa[i][j])
            {
            case 'R':
            {
                a[i][j+1]=0;
                r.x=i;
                r.y=j+1;
            }
            break;
            case 'J':
            {
                a[i][j+1]=0;
                ju.x=i;
                ju.y=j+1;
            }
            break;
            case ' ':
                a[i][j+1]=0;
                break;
            case 'X':
                a[i][j+1]=-1;
                break;
            }
    fclose(f);
}
int main()
{
    int n,m,**a;
    citire(n,m,a,"rj.in");
    int i,j;
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<"\n";
    }*/
    str coada[10001];
    int viz[101][101],k=0,l=0;
    for(i=0; i<=100; i++)
        for(j=0; j<=100; j++) viz[i][j]=0;
    coada[l]=r;
    viz[coada[l].x][coada[l].y]=1;
    a[coada[l].x][coada[l].y]=1;
    while(l>=k)
    {
        if(coada[k].x-1>=1)
            if(!viz[coada[k].x-1][coada[k].y]&&!a[coada[k].x-1][coada[k].y])
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y;
                viz[coada[k].x-1][coada[k].y]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].x+1<=n)
            if(!viz[coada[k].x+1][coada[k].y]&&!a[coada[k].x+1][coada[k].y])
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y;
                viz[coada[k].x+1][coada[k].y]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].y-1>=1)
            if(!viz[coada[k].x][coada[k].y-1]&&!a[coada[k].x][coada[k].y-1])
            {
                coada[++l].x=coada[k].x;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x][coada[k].y-1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].y+1<=m)
            if(!viz[coada[k].x][coada[k].y+1]&&!a[coada[k].x][coada[k].y+1])
            {
                coada[++l].x=coada[k].x;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x][coada[k].y+1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].x-1>=1&&coada[k].y-1>=1)
            if(!viz[coada[k].x-1][coada[k].y-1]&&!a[coada[k].x-1][coada[k].y-1])
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x-1][coada[k].y-1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }

        if(coada[k].x+1<=n&&coada[k].y-1>=1)
            if(!viz[coada[k].x+1][coada[k].y-1]&&!a[coada[k].x+1][coada[k].y-1])
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x+1][coada[k].y-1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].x+1<=n&&coada[k].y+1<=m)
            if(!viz[coada[k].x+1][coada[k].y+1]&&!a[coada[k].x+1][coada[k].y+1])
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x+1][coada[k].y+1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        if(coada[k].x-1>=1&&coada[k].y+1<=m)
            if(!viz[coada[k].x-1][coada[k].y+1]&&!a[coada[k].x-1][coada[k].y+1])
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x-1][coada[k].y+1]=1;
                a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
            }
        //cout<<coada[k].x<<" "<<coada[k].y<<"\n";
        k++;
    }
    for(i=0; i<=100; i++)
        for(j=0; j<=100; j++) viz[i][j]=0;
    k=l=0;
    int h=100,b=100,v=10000;
    coada[l]=ju;
    viz[coada[l].x][coada[l].y]=1;
    a[coada[l].x][coada[l].y]=1;
    while(l>=k)
    {
        if(coada[k].x-1>=1)
            if(!viz[coada[k].x-1][coada[k].y]&&a[coada[k].x-1][coada[k].y]!=-1)
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y;
                viz[coada[k].x-1][coada[k].y]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].x+1<=n)
            if(!viz[coada[k].x+1][coada[k].y]&&a[coada[k].x+1][coada[k].y]!=-1)
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y;
                viz[coada[k].x+1][coada[k].y]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].y-1>=1)
            if(!viz[coada[k].x][coada[k].y-1]&&a[coada[k].x][coada[k].y-1]!=-1)
            {
                coada[++l].x=coada[k].x;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x][coada[k].y-1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].y+1<=m)
            if(!viz[coada[k].x][coada[k].y+1]&&a[coada[k].x][coada[k].y+1]!=-1)
            {
                coada[++l].x=coada[k].x;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x][coada[k].y+1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].x-1>=1&&coada[k].y-1>=1)
            if(!viz[coada[k].x-1][coada[k].y-1]&&a[coada[k].x-1][coada[k].y-1]!=-1)
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x-1][coada[k].y-1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }

        if(coada[k].x+1<=n&&coada[k].y-1>=1)
            if(!viz[coada[k].x+1][coada[k].y-1]&&a[coada[k].x+1][coada[k].y-1]!=-1)
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y-1;
                viz[coada[k].x+1][coada[k].y-1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].x+1<=n&&coada[k].y+1<=m)
            if(!viz[coada[k].x+1][coada[k].y+1]&&a[coada[k].x+1][coada[k].y+1]!=-1)
            {
                coada[++l].x=coada[k].x+1;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x+1][coada[k].y+1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        if(coada[k].x-1>=1&&coada[k].y+1<=m)
            if(!viz[coada[k].x-1][coada[k].y+1]&&a[coada[k].x-1][coada[k].y+1]!=-1)
            {
                coada[++l].x=coada[k].x-1;
                coada[l].y=coada[k].y+1;
                viz[coada[k].x-1][coada[k].y+1]=1;
                if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1) a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
                else if(a[coada[l].x][coada[l].y]<=v)
                    if(coada[l].x<=h)
                    {
                        h=coada[l].x;
                        b=coada[l].y;
                        v=a[coada[l].x][coada[l].y];
                    };
            }
        k++;
    }
    ofstream g("rj.out");
    g<<v<<" "<<h<<" "<<b<<"\n";
    g.close();
    return 0;
}