Mai intai trebuie sa te autentifici.

Cod sursa(job #1894672)

Utilizator CroitoruAlinCroitoru Alin CroitoruAlin Data 27 februarie 2017 12:34:20
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <math.h>
using namespace std;
struct punct
{
    int x,y;
};
void citire(int &n,int &m,char **&M)
{
    ifstream fin("rj.in");
    fin>>n>>m;
    M=new char* [n+1];
    int i,j;
    for(i=1;i<=n;i++)
        M[i]=new char [m+1];
    for(i=1;i<=n;i++){
            fin.get();
        for(j=1;j<=m;j++)
            fin.get(M[i][j]);
    }
    fin.close();
}
void lee(char **M,punct r,punct j,int n,int m)
{
    queue <punct> c1,c2;
    c1.push(r);
    c2.push(j);
    punct a,b,a1,b1;
    int i;
    int oriz[8]={1,1,1,0,0,-1,-1,-1};
    int vert[8]={0,1,-1,1,-1,0,1,-1};
    while(!c1.empty() || !c2.empty())
    {
        if(!c1.empty());
        a=c1.front();
        if(!c2.empty())
        b=c2.front();
        for(i=0;i<8;i++)
        {
            a1.x=a.x+oriz[i];
            a1.y=a.y+vert[i];
            if(a1.x>0 && a1.x<n+1 && a1.y>0 && a1.y<m+1)
            if(M[a1.x][a1.y]==' ' || M[a1.x][a1.y]=='J')
            {
                //cout<<a1.x<<" "<<a1.y<<"\n";
              c1.push(a1);
              if(M[a1.x][a1.y]=='J')
              M[a1.x][a1.y]='Z';
              else
                M[a1.x][a1.y]='R';
            }

        }
        for(i=0;i<8;i++)
        {
            b1.x=b.x+oriz[i];
            b1.y=b.y+vert[i];
             if(b1.x>0 && b1.x<n+1 && b1.y>0 && b1.y<m+1){
            if(M[b1.x][b1.y]==' ' || M[b1.x][b1.y]=='R')
            {
               // cout<<b1.x<<" "<<b1.y<<"\n";
              c2.push(b1);
              if(M[b1.x][b1.y]=='R')
              M[b1.x][b1.y]='Z';
              else
                M[b1.x][b1.y]='J';

            }

            }
        }
        c1.pop();
        c2.pop();
    }
}
int distanta_Manhattan(punct a,punct b)
{
    return fabs(a.x-b.x)+fabs(a.y-b.y);
}
int main()
{
    char **M;
    int n,m;
    citire(n,m,M);
    punct r,jl;
    int i,j,sw=0;
    for(i=1;i<=n;i++){
        if(sw==3)
        break;
    for(j=1;j<=m;j++){
            if(M[i][j]=='R')
               {
                   sw++;
                   r.x=i;
                   r.y=j;
               }
               if(M[i][j]=='J')
               {
                   sw++;
                   jl.x=i;
                   jl.y=j;
               }
               if(sw==2){
                break;
                sw=3;}
    }
    }
    lee(M,r,jl,n,m);
    punct a;
    int minn=m*n,xmin,ymin;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
           if(M[i][j]=='Z')
           {
             a.x=i;
             a.y=j;
             if(distanta_Manhattan(r,a)==distanta_Manhattan(jl,a))
                if(minn>distanta_Manhattan(r,a))
             {
                 minn=distanta_Manhattan(r,a);
                xmin=a.x;
                ymin=a.y;
             }
           }
    ofstream fout("rj.out");
    fout<<minn<<" "<<xmin<<" "<<ymin<<" "<<'\n';
    fout.close();
    return 0;
}