Cod sursa(job #1894730)

Utilizator CroitoruAlinCroitoru Alin CroitoruAlin Data 27 februarie 2017 13:47:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <math.h>
using namespace std;
struct punct
{
    int x,y,d;
};
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,int **&M1,int **&M2)
{
    queue <punct> c1,c2;
    c1.push(r);
    c2.push(j);
    punct a,b,a1,b1;
    int i;
     M1=new int*[n+1];
     M2=new int*[n+1];
    for(i=1;i<=n;i++){
        M1[i]=new int [m+1];
        M2[i]=new int [m+1];
    }
    int k;
    for(i=1;i<=n;i++)
        for(k=1;k<=m;k++)
            M1[i][k]=M2[i][k]=0;
    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.d=a.d+1;
            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);
              M1[a1.x][a1.y]=a1.d;
              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.d=b.d+1;
            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);
              M2[b1.x][b1.y]=b1.d;
              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 main()
{
    char **M;
    int n,m;
    citire(n,m,M);
    punct r,jl;
    int i,j,sw=0;

    int **M1,**M2;
 for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){
            if(M[i][j]=='R')
               {
                   r.x=i;
                   r.y=j;
                   r.d=1;
               }
               else
               if(M[i][j]=='J')
               {
                   jl.x=i;
                   jl.y=j;
                   jl.d=1;
               }

    }
    lee(M,r,jl,n,m,M1,M2);

    punct a;
    int minn=m*n,xmin=0,ymin=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
           if(M[i][j]=='Z')
           {

             a.x=i;
             a.y=j;
             if(M1[i][j]==M2[i][j] )
             {
                if(minn>M1[i][j])
             {

                 minn=M1[i][j];
                xmin=a.x;
                ymin=a.y;
             }
           }
           }
           for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            cout<<M1[i][j]<<" ";
        cout<<'\n';}
    ofstream fout("rj.out");
    fout<<minn<<" "<<xmin<<" "<<ymin;
    fout.close();
    return 0;
}