Cod sursa(job #2414016)

Utilizator Galatanu_BogdanGalatanu Bogdan Ioan Galatanu_Bogdan Data 23 aprilie 2019 22:40:07
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 150
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int map[NMAX][NMAX];
int map2[NMAX][NMAX];
int n,m;
int di[8] ={1,1,-1,-1,0,0,1,-1};
int dj[8] ={1,-1,1,-1,1,-1,0,0};
queue< pair<int,int> >coada;
int pozStartx,pozStarty,pozStopx,pozStopy;
void Read()
{
    int i,j;char aux[102];
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {       fin.get();
        fin.get(aux,102);
        for(j=0;j<m;j++)
        {
            if(aux[j]==' ')
                map[i][j+1]=0;
            if(aux[j]=='X')
                map[i][j+1]=-1;
            if(aux[j]=='R')
            { map[i][j+1]=1;
                pozStartx=i;
                pozStarty=j+1;
            }
            if(aux[j]=='J')
            { map[i][j+1]=1;
                pozStopx=i;
                pozStopy=j+1;
            }
            map2[i][j+1]=map[i][j+1];
        }
    }
}
bool OK(int i,int j)
{
    if(map[i][j]== -1)
        return false;
    if(i<1 || j<1 || i>n || j>m)
        return false;
    
return true;
}
bool OK2(int i,int j)
{
    if(map2[i][j]== -1)
        return false;
    if(i<1 || j<1 || i>n || j>m)
        return false;
    
    return true;
}
void Lee()
{
    int i,j,i_urmator,j_urmator;
    map[pozStartx][pozStarty]=1;
    coada.push(make_pair(pozStartx, pozStarty));
    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( OK(i_urmator, j_urmator) && map[i_urmator][j_urmator] <1 ){
                map[i_urmator][j_urmator]=map[i][j]+1;
                coada.push( make_pair(i_urmator, j_urmator) );
            }
        }
        
        
    }
}
void Lee2()
{
    int i,j,i_urmator,j_urmator;
    coada.push(make_pair(pozStopx, pozStopy));
    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( OK2(i_urmator, j_urmator) && map2[i_urmator][j_urmator] <1 ){
                map2[i_urmator][j_urmator]=map2[i][j]+1;
                coada.push( make_pair(i_urmator, j_urmator) );
            }
        }
        
        
    }
}
int main()
{
    Read();
    Lee();
    Lee2();
    int tmin=9999,save_x=0,save_y=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(map[i][j]==map2[i][j] && map[i][j]>1 && map2[i][j]>1 && map[i][j]<tmin)
            {
                tmin=map[i][j];
                save_x=i;
                save_y=j;
                
                
            }
    }
    fout<<tmin<<" "<<save_x<<" "<<save_y;
        return 0;
}