Cod sursa(job #1621866)

Utilizator ArminaMoldovanMoldovan Armina ArminaMoldovan Data 29 februarie 2016 22:23:25
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<fstream>
#include<queue>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

queue< pair < int, int > > coada;

int di[8]={0, 0, 1, -1, 1, -1, 1, -1};
int dj[8]={1, -1, 0, 0, 1, 1, -1, -1};

int MapJUL[101][101];
int MapROM[101][101];

int n, m, i, j, startxr, startyr, startxj, startyj;

void read()
{
    char s[101];
    fin>>n>>m;

    fin.getline(s, 101);
    for(i=1; i<=n; i++)
    {
        fin.getline(s, 101);
        for(j=0; j<m; j++)
        {
            if(s[j]=='R')  { MapROM[i][j+1]=1;  startxr=i;   startyr=j+1;}//pozitia pe care se afla romeo
            else if(s[j]=='X')  MapROM[i][j+1]=-1;//un obstacol
            else if(s[j]==' ')  MapROM[i][j+1]=0; //daca am spatiu marchez cu 0
            else if(s[j]=='J') { MapROM[i][j+1]=0; startxj=i; startyj=j+1;}//pozitia julietei
        }
    }
}
bool ok(int i, int j)
{
    if(i<1 || j<1 || i>n|| j>m) return false;
    if(MapJUL[i][j]==-1 || MapJUL[i][j]==-1)    return false;
    return true;

}
bool ok1(int i, int j)
{
    if(i<1 || j<1 || i>n || j>m)    return false;
    if(MapROM[i][j]==-1 || MapROM[i][j]==-1)    return false;
    return true;
}
void lee_ROM()
{
 int i_urmator, j_urmator;
 coada.push(make_pair(startxr, startyr));
 while(!coada.empty())
 {
     i=coada.front().first;
     j=coada.front().second;
     coada.pop();
     for(int directie=0; directie<8; directie++)
     {
         i_urmator=i+di[directie];
         j_urmator=j+dj[directie];
         if(ok1(i_urmator, j_urmator) && MapROM[i_urmator][j_urmator]<1)
         {
             MapROM[i_urmator][j_urmator]=MapROM[i][j]+1;

         coada.push(make_pair(i_urmator, j_urmator));
         }
     }
 }
  /*for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            fout<<MapROM[i][j]<<" ";
        }
        fout<<endl;

    } */
}
void lee_JUL()
{
    int i_urm, j_urm;
    coada.push(make_pair(startxj, startyj));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int dir=0; dir<8; dir++)
        {
            i_urm=i+di[dir];
            j_urm=j+dj[dir];
            if(ok(i_urm, j_urm) && MapJUL[i_urm][j_urm]<1)
            {
                MapJUL[i_urm][j_urm]=MapJUL[i][j]+1;
                coada.push(make_pair(i_urm, j_urm));
            }
        }
    }
     /*for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            fout<<MapJUL[i][j]<<" ";
        }
        fout<<endl;

    } */
}
void dadada()
{
    int minim=999999, stopx, stopy;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(MapJUL[i][j]==MapROM[i][j] && MapJUL[i][j]<minim && MapJUL[i][j]>0 && MapROM[i][j]>0)
            {
                stopx=i;
                stopy=j;
                minim=MapJUL[i][j];
            }
        }
    }
    fout<<MapJUL[stopx][stopy]<<" "<<stopx<<" "<<stopy;
}

int main()
{
    read();
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
           MapJUL[i][j]= MapROM[i][j];
           // fout<<MapJUL[i][j]<<" ";//se afiseaza bine matricele
        }
       // fout<<endl;
       MapJUL[startxr][startyr]=0;
       MapJUL[startxj][startyj]=1;
    }
    lee_ROM();
    lee_JUL();
    dadada();
}