Cod sursa(job #742187)

Utilizator visanrVisan Radu visanr Data 28 aprilie 2012 21:37:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.78 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <iostream.h>

using namespace std;

struct vecin
{
       int i,j;
};

int **rom,**jul,n,m,i,j;

void citire()
{
     scanf("%i", &n);
     scanf("%i", &m);    
     rom=(int **)calloc(n,sizeof(int *));
     for(i=0;i<n;i++)
     {
                    rom[i]=(int *)calloc(m,sizeof(int));
     }
     jul=(int **)calloc(n,sizeof(int *));
     for(i=0;i<n;i++)
     {
                    jul[i]=(int *)calloc(m,sizeof(int));
     }
     char car;
     for(i=0;i<n;i++)
     {
                     for(j=0;j<m;j++)
                     {
                                     scanf("%c", &car);
                                     if(car==' ')
                                     {
                                                  rom[i][j]=0;
                                                  jul[i][j]=0;
                                     }else
                                     if(car=='X')
                                     {
                                                    rom[i][j]=-1;
                                                    jul[i][j]=-1;
                                     }else
                                     if(car=='R')
                                     {
                                                    rom[i][j]=1;
                                                    jul[i][j]=0;
                                     }else
                                     if(car=='J')
                                     {
                                                    jul[i][j]=1;
                                                    rom[i][j]=0;
                                     }else j--;
                     }
     }
}


void Lee(int i1,int j1,int **m1)
{
     queue<vecin> q;
     vecin vv;
     vv.i=i1;
     vv.j=j1;
     q.push(vv);
     while(!q.empty())
     {
                      vecin vechi=q.front();
                      q.pop();
                      if(vechi.i-1>=0)
                      {
                                      if(m1[vechi.i-1][vechi.j]==0)
                                      {
                                                    m1[vechi.i-1][vechi.j]=m1[vechi.i][vechi.j]+1;
                                                    vecin vvv;
                                                    vvv.i=vechi.i-1;
                                                    vvv.j=vechi.j;
                                                    q.push(vvv);
                                      }
                      }
                      if(vechi.i+1<=n-1)
                      {
                                      if(m1[vechi.i+1][vechi.j]==0)
                                      {
                                                    m1[vechi.i+1][vechi.j]=m1[vechi.i][vechi.j]+1;
                                                    vecin vvv;
                                                    vvv.i=vechi.i+1;
                                                    vvv.j=vechi.j;
                                                    q.push(vvv);
                                      }
                      }
                      if(vechi.j-1>=0)
                      {
                                      if(m1[vechi.i][vechi.j-1]==0)
                                      {
                                                    m1[vechi.i][vechi.j-1]=m1[vechi.i][vechi.j]+1;
                                                    vecin vvv;
                                                    vvv.i=vechi.i;
                                                    vvv.j=vechi.j-1;
                                                    q.push(vvv);
                                      }
                      }
                      if(vechi.j+1<=m-1)
                      {
                                      if(m1[vechi.i][vechi.j+1]==0)
                                      {
                                                    m1[vechi.i][vechi.j+1]=m1[vechi.i][vechi.j]+1;
                                                    vecin vvv;
                                                    vvv.i=vechi.i;
                                                    vvv.j=vechi.j+1;
                                                    q.push(vvv);
                                      }
                      }
                      if(vechi.i-1>=0 && vechi.j-1>=0)
                      {
                                      if(m1[vechi.i-1][vechi.j-1]==0)
                                      {
                                                        m1[vechi.i-1][vechi.j-1]=m1[vechi.i][vechi.j]+1;
                                                        vecin vvv;
                                                        vvv.i=vechi.i-1;
                                                        vvv.j=vechi.j-1;
                                                        q.push(vvv);
                                      }
                      }
                      if(vechi.i-1>=0 && vechi.j+1<=m-1)
                      {
                                      if(m1[vechi.i-1][vechi.j+1]==0)
                                      {
                                                        m1[vechi.i-1][vechi.j+1]=m1[vechi.i][vechi.j]+1;
                                                        vecin vvv;
                                                        vvv.i=vechi.i-1;
                                                        vvv.j=vechi.j+1;
                                                        q.push(vvv);
                                      }
                      }
                      if(vechi.i+1<=n-1 && vechi.j-1>=0)
                      {
                                      if(m1[vechi.i+1][vechi.j-1]==0)
                                      {
                                                        m1[vechi.i+1][vechi.j-1]=m1[vechi.i][vechi.j]+1;
                                                        vecin vvv;
                                                        vvv.i=vechi.i+1;
                                                        vvv.j=vechi.j-1;
                                                        q.push(vvv);
                                      }
                      }
                      if(vechi.i+1<=n-1 && vechi.j+1<=m-1)
                      {
                                      if(m1[vechi.i+1][vechi.j+1]==0)
                                      {
                                                        m1[vechi.i+1][vechi.j+1]=m1[vechi.i][vechi.j]+1;
                                                        vecin vvv;
                                                        vvv.i=vechi.i+1;
                                                        vvv.j=vechi.j+1;
                                                        q.push(vvv);
                                      }
                      }
     }
}

void rj()
{
     int min=1000,pozi,pozj;
     for(i=0;i<n;i++)
     {
                     for(j=0;j<m;j++)
                     {
                                     if(rom[i][j]==jul[i][j] && rom[i][j]!=-1 && rom[i][j]!=0)
                                     {
                                                           if(rom[i][j]<min)
                                                           {
                                                                            min=rom[i][j];
                                                                            pozi=i+1;
                                                                            pozj=j+1;
                                                           }
                                     }
                     }
     }
     printf("%i %i %i", min,pozi,pozj);
}

int main ()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int i,j,x1=0,y1=0,x2=0,y2=0;
    citire();
    for(i=0;i<n;i++)
    {
                    for(j=0;j<m;j++)
                    {
                                    if(rom[i][j]==1)
                                    {
                                                    x1=i;
                                                    y1=j;
                                    }
                    }
    }
    for(i=0;i<n;i++)
    {
                    for(j=0;j<m;j++)
                    {
                                    if(jul[i][j]==1)
                                    {
                                                    x2=i;
                                                    y2=j;
                                    }
                    }
    }
    Lee(x1,y1,rom);
    Lee(x2,y2,jul);
    rj();
    scanf("%i", &i);
    return 0;
}