Cod sursa(job #891409)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 25 februarie 2013 16:36:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 12.22 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
struct element {unsigned char x,y;}c[10500];
struct vector {int val;bool atins;}v[105][105];
int n,i,j,m,xRomeo,xJulieta,yRomeo,yJulieta,g,mini=999999,minj=99999,pasmaxim=9999999,pas;
char s[130];
void Lee_Romeo(int x1,int y1,int x2,int y2)
{
    int st=1,dr=1,i,j;
    c[st].x=x1;
    c[st].y=y1;
    v[x1][y1].val=1;
    while(st<=dr)
    {
            i=c[st].x;
            j=c[st].y;
            if(v[i][j].val+1<v[i][j-1].val)
                        {
                             dr++;
                             c[dr].x=i;
                             c[dr].y=j-1;
                             v[i][j-1].val=v[i][j].val+1;
                        }

                if(v[i][j].val+1<v[i+1][j-1].val)
                {
                     dr++;
                     c[dr].x=i+1;
                     c[dr].y=j-1;
                     v[i+1][j-1].val=v[i][j].val+1;
                }
                if(v[i][j].val+1<v[i-1][j-1].val )
                {
                     dr++;
                     c[dr].x=i-1;
                     c[dr].y=j-1;
                     v[i-1][j-1].val=v[i][j].val+1;
                }
                  if(v[i][j].val+1<v[i][j+1].val)
                {
                     dr++;
                     c[dr].x=i;
                     c[dr].y=j+1;
                     v[i][j+1].val=v[i][j].val+1;
                }
                    if(v[i][j].val+1<v[i+1][j+1].val)
                {
                     dr++;
                     c[dr].x=i+1;
                     c[dr].y=j+1;
                     v[i+1][j+1].val=v[i][j].val+1;
                }
                        if(v[i][j].val+1<v[i-1][j+1].val)
                {
                     dr++;
                     c[dr].x=i-1;
                     c[dr].y=j+1;
                     v[i-1][j+1].val=v[i][j].val+1;
                }
                    if(v[i][j].val+1<v[i+1][j].val)
                {
                     dr++;
                     c[dr].x=i+1;
                     c[dr].y=j;
                     v[i+1][j].val=v[i][j].val+1;
                }
                     if(v[i][j].val+1<v[i-1][j].val)
                {
                     dr++;
                     c[dr].x=i-1;
                     c[dr].y=j;
                     v[i-1][j].val=v[i][j].val+1;
                }

            st++;
    }

}
void Lee_Julieta(int x1,int y1,int x2,int y2)
{
    int st=1,dr=1,i,j,ok=1;
    c[st].x=x1;
    c[st].y=y1;
    v[x1][y1].val=1;
    while(st<=dr)
    {
            i=c[st].x;
            j=c[st].y;
            if(v[i][j].val+1==v[i][j-1].val && v[i][j-1].atins==0)
                        {
                            ok=0;
                            if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                            if(i<mini)
                                {
                                    mini=i;
                                    minj=j-1;
                                }
                            if(i==mini)
                                {
                                    if(j-1<minj)
                                        minj=j-1;
                                }
                            }
                        }
                else
                if(v[i][j].val+1<v[i][j-1].val)
                        {
                             dr++;
                             c[dr].x=i;
                             c[dr].y=j-1;
                             v[i][j-1].val=v[i][j].val+1;
                             v[i][j-1].atins=1;

                        }



                if(v[i][j].val+1==v[i+1][j-1].val&&v[i+1][j-1].atins==0)
                        {
                            ok=0;
                             if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                             if(i+1<mini)
                                {
                                    mini=i+1;
                                    minj=j-1;
                                }
                            if(i+1==mini)
                                {
                                    if(j-1<minj)
                                        minj=j-1;
                                }
                            }
                        }
                else
                    if(v[i][j].val+1<v[i+1][j-1].val)
                        {
                             dr++;
                             c[dr].x=i+1;
                             c[dr].y=j-1;
                             v[i+1][j-1].val=v[i][j].val+1;
                             v[i+1][j-1].atins=1;
                        }
            if(v[i][j].val+1==v[i-1][j-1].val&&v[i-1][j-1].atins==0)
                            {
                                ok=0;
                                 if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                             if(i-1<mini)
                                {
                                    mini=i-1;
                                    minj=j-1;
                                }
                             if(i-1==mini)
                                {
                                    if(j-1<minj)
                                        minj=j-1;
                                }
                            }
                        }
                else
                    if(v[i][j].val+1<v[i-1][j-1].val)
                            {
                                 dr++;
                                 c[dr].x=i-1;
                                 c[dr].y=j-1;
                                 v[i-1][j-1].val=v[i][j].val+1;
                                 v[i-1][j-1].atins=1;
                            }
                if(v[i][j].val+1==v[i][j+1].val&&v[i][j+1].atins==0)
                        {
                            ok=0;
                             if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                            if(i<mini)
                                {
                                    mini=i;
                                    minj=j+1;
                                }
                            if(i==mini)
                                {
                                    if(j+1<minj)
                                        minj=j+1;
                                }
                            }
                        }
                else
                  if(v[i][j].val+1<v[i][j+1].val)
                {
                     dr++;
                     c[dr].x=i;
                     c[dr].y=j+1;
                     v[i][j+1].val=v[i][j].val+1;
                     v[i][j+1].atins=1;
                }

                if(v[i][j].val+1==v[i+1][j+1].val && v[i+1][j+1].atins==0)
                        {
                            ok=0;
                             if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                            if(i+1<mini)
                                {
                                    mini=i+1;
                                    minj=j+1;
                                }
                            if(i+1==mini)
                                {
                                    if(j+1<minj)
                                        minj=j+1;
                                }
                            }
                        }
                else
                    if(v[i][j].val+1<v[i+1][j+1].val)
                {
                     dr++;
                     c[dr].x=i+1;
                     c[dr].y=j+1;
                     v[i+1][j+1].val=v[i][j].val+1;
                     v[i+1][j+1].atins=1;
                }
                if(v[i][j].val+1==v[i-1][j+1].val && v[i-1][j+1].atins==0)
                        {
                            ok=0;
                             if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                             if(i-1<mini)
                                {
                                    mini=i-1;
                                    minj=j+1;
                                }
                            if(i-1==mini)
                                {
                                    if(j+1<minj)
                                        minj=j+1;
                                }
                            }
                        }
                    else
                        if(v[i][j].val+1<v[i-1][j+1].val)
                {
                     dr++;
                     c[dr].x=i-1;
                     c[dr].y=j+1;
                     v[i-1][j+1].val=v[i][j].val+1;
                     v[i-1][j+1].atins=1;
                }
                 if(v[i][j].val+1==v[i+1][j].val && v[i+1][j].atins==0)
                        {
                            ok=0;
                             if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                             if(i+1<mini)
                                {
                                    mini=i+1;
                                    minj=j;
                                }
                            if(i+1==mini)
                                {
                                    if(j<minj)
                                        minj=j;
                                }
                            }
                        }
                    else
                    if(v[i][j].val+1<v[i+1][j].val)
                {
                     dr++;
                     c[dr].x=i+1;
                     c[dr].y=j;
                     v[i+1][j].val=v[i][j].val+1;
                     v[i+1][j].atins=1;
                }
                if(v[i][j].val+1==v[i-1][j].val && v[i-1][j].atins==0)
                    {
                        ok=0;
                         if(pas<=pasmaxim)
                            {
                                pasmaxim=pas;

                         if(i-1<mini)
                                {
                                    mini=i-1;
                                    minj=j;
                                }
                            if(i-1==mini)
                                {
                                    if(j<minj)
                                        minj=j;
                                }
                            }
                    }
                    else
                     if(v[i][j].val+1<v[i-1][j].val)
                {
                     dr++;
                     c[dr].x=i-1;
                     c[dr].y=j;
                     v[i-1][j].val=v[i][j].val+1;
                     v[i-1][j].atins=1;
                }
            pas=v[i][j].val+1;
            st++;
    }

}

int main()
{
    in>>n>>m;
    in.getline(s,104);
    for(i=1;i<=n;i++)
        {
            in.getline(s,104);
                for(j=1;j<=m;j++)
                    {
                    if(s[j-1]=='X')
                        v[i][j].val=-1;
                    else
                        if(s[j-1]=='R')
                            {
                                xRomeo=i;
                                yRomeo=j;
                            }
                    else
                        if(s[j-1]=='J')
                            {
                                xJulieta=i;
                                yJulieta=j;
                            }
                    else
                        v[i][j].val=99999999;
                    }


        }
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++)
            if(i==0||i==n+1||j==0||j==m+1)
                v[i][j].val=-10000000;
    Lee_Romeo(xRomeo,yRomeo,xJulieta,yJulieta);
    Lee_Julieta(xJulieta,yJulieta,xRomeo,yRomeo);
    out<<v[mini][minj].val<<" "<<mini<<" "<<minj<<'\n';
    out.close();
    in.close();
    return 0;
}