Cod sursa(job #2414593)

Utilizator Galatanu_BogdanGalatanu Bogdan Ioan Galatanu_Bogdan Data 24 aprilie 2019 19:42:46
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.88 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;
//}
//
//
//
//
//
//
//
#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[160];
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {       fin.get();
        fin.get(aux,150);
        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;
}