Cod sursa(job #876598)

Utilizator YoYoxxIftimesei Ioan YoYoxx Data 11 februarie 2013 22:18:33
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <fstream>
#include <iostream>
#include<string.h>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n,m,x1,x2,y1,y2,sol=0;
const int dx[]={0,1,1,1,0,-1,-1,-1};
const int dy[]={1,1,0,-1,-1,-1,0,1};
int mat[103][103];
struct c
{
    int px[100404];
    int py[100404];
}c;
struct s
{
    int px[10404];
    int py[10404];
    int val[10404];
}s;

void citire()
{
    int i,j;
    char v[105];
    in>>n>>m;
    for(i=0;i<=n;i++)
    {
        in.getline(v,m+1);
        for(j=1;j<=m;j++)
       {
           if(v[j-1]=='R')
           {
               mat[i][j]=1;
               x1=i;
               y1=j;
           }
           if(v[j-1]=='J')
           {
               mat[i][j]=0;
               x2=i;
               y2=j;
           }
           if(v[j-1]=='X')mat[i][j]=-1;
           if(v[j-1]==' ') mat[i][j]=0;
       }
    }

}

void bordare()
{
    int i,j;
    for (i=0;i<=n+1;i++)
    {
        mat[0][i]=-1;
        mat[m+1][i]=-1;
    }
    for(i=0;i<=m;i++)
    {
        mat[i][0]=-1;
        mat[i][n+1]=-1;
    }
}

void lee(int z,int w,int t,int y)
{
    int a,b,k,prim=0,ultim=0;
    c.px[prim]=z;
    c.py[prim]=w;


    while (prim<=ultim&&mat[t][y]==0)
    {
        a=c.px[prim];
        b=c.py[prim];
        prim++;

            for(k=0;k<8;k++)
            {


               if( (mat[a+dx[k]][b+dy[k]]==0||mat[a][b]+1<=mat[a+dx[k]][b+dy[k]])&& (mat[a+dx[k]][b+dy[k]]!=-1) )
                {

               ultim++;
               c.px[ultim]=a+dx[k];
               c.py[ultim]=b+dy[k];
               mat[a+dx[k]][b+dy[k]]=mat[a][b]+1;
                }


            }

    }
}

void rezultat(int q,int w)
{
    int a,b,ultim=0,prim=0,ok=1,k;
    c.px[prim]=x1;
    c.py[prim]=y1;
    while(prim<=ultim)
    {
        a=c.px[prim];
        b=c.py[prim];
        prim++;
        for(k=0;k<8;k++)
        {
            if(mat[a+dx[k]][b+dy[k]]==mat[a][b]+1&mat[a+dx[k]][b+dy[k]]!=-1)
            {
                ultim++;
                c.px[ultim]=a+dx[k];
                c.py[ultim]=b+dy[k];
            }
            else if(mat[a+dx[k]][b+dy[k]]+1==mat[a][b]&&mat[a+dx[k]][b+dy[k]]!=-1)
            {
                s.px[sol]=a;
                s.py[sol]=b;
                s.val[sol]=mat[a][b];
               sol++;
            }
        }
        mat[a][b]=-1;
    }


}

int main()
{
    int i,j,mini=10404,mini2=102,mini3=103;
    citire();
    bordare();
    lee(x1,y1,x2,y2);
    mat[x1][y1]=0;
    mat[x2][y2]=1;
    lee(x2,y2,x1,y1);
    mat[x1][y1]=1;
    rezultat(x1,y1);

    for(i=0;i<sol;i++)
    {
     if(s.val[i]<mini)mini=s.val[i];
    }

for(i=0;i<sol;i++)
{
    if(s.val[i]==mini&&s.px[i]<mini2)
        {
            mini2=s.px[i];
            mini3=s.py[i];
        }
}
for(i=0;i<sol;i++)
{
    if(s.val[i]==mini&&s.px[i]==mini2&&s.py[i]<mini3) mini3=s.py[i];
}


out<<mini<<" "<<mini2<<" "<<mini3;
in.close();
out.close();
return 0;
}