Cod sursa(job #1140363)

Utilizator cioionutFMI Ionut Ciocoiu cioionut Data 11 martie 2014 22:28:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 11.65 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);
    //for (i=0;i<m;i++) cout<<i<<aa[1][i];
    //for(i=0;i<=n;i++) {cout<<i;puts(aa[i]);}
    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[101];
    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;
    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 break;
                                                           }
        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 break;
                                                           }
        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 break;
                                                           }
        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 break;
                                                           }
        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 break;
                                                }

        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 break;
                                                }
        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 break;
                                                }
        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 break;
                                                }
    //cout<<coada[k].x<<" "<<coada[k].y<<"\n";
    k++;
    }
    //cout<<k<<" "<<l<<"\n";
    ofstream g("rj.out");
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            //cout<<a[i][j]<<" ";
        //cout<<"\n";
            if(a[coada[l].x][coada[l].y]==a[i][j]) {g<<a[coada[l].x][coada[l].y]<<" "<<i<<" "<<j<<"\n";break;}
    g.close();
    return 0;
}