Cod sursa(job #1880813)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 15 februarie 2017 22:16:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include    <fstream>
#include    <queue>
#include    <cstring>

using namespace std;


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

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

int Map[101][101] , N , M , Time , fx , fy;
int startx , starty , stopx , stopy;


queue < pair < int, int > > coada;


void Read(){char p[101];

    fin>> N >> M;
    fin.get();
    for(int i=1;i<=N;i++){

        fin.getline(p,101);

        for(int k=0;k<strlen(p);k++){
            if(p[k]=='X')Map[i][k+1]=-1;
            if(p[k]=='R')startx=i,starty=k+1;
            if(p[k]=='J')stopx=i,stopy=k+1;
        }

    }

}

bool OK(int i,int j){

    if(i<1 || j<1 || i>N || j>M)
            return false;

    if(Map[i][j]==-1 || (i==startx && j==starty))
            return false;

    return true;

}
void Lee(){

    int i , j , i_next , j_next;
    Map[startx][starty]=1;
    coada.push( make_pair(startx , starty) );

    while( !coada.empty() ){

        i = coada.front().first;
        j = coada.front().second;
        coada.pop();

        for(int directie = 0 ; directie < 9 ; directie++){

            i_next = i + di[directie];
            j_next = j + dj[directie];

            if(OK(i_next,j_next) && Map[i_next][j_next]<1){
                coada.push( make_pair(i_next , j_next) );
                Map[i_next][j_next] = Map[i][j] + 1;
            }

        }

    }

}

void rec(int i,int j,int &fx,int &fy){

    if(Map[i][j]!=Time){

            if(Map[i+1][j]==Map[i][j]-1 && i<N)rec(i+1,j,fx,fy);
            if(Map[i][j+1]==Map[i][j]-1 && j<M)rec(i,j+1,fx,fy);
            if(Map[i-1][j]==Map[i][j]-1 && i>1)rec(i-1,j,fx,fy);
            if(Map[i][j-1]==Map[i][j]-1 && j>1)rec(i,j-1,fx,fy);
            if(Map[i+1][j+1]==Map[i][j]-1 && j<M && i<N)rec(i+1,j+1,fx,fy);
            if(Map[i-1][j-1]==Map[i][j]-1 && j>1 && i>1)rec(i-1,j-1,fx,fy);
            if(Map[i-1][j+1]==Map[i][j]-1 && i>N && j<M)rec(i-1,j+1,fx,fy);
            if(Map[i+1][j-1]==Map[i][j]-1 && j>1 && i<N)rec(i+1,j-1,fx,fy);

    }else fx=i,fy=j;

}

int main()
{
    Read();
    Lee();

    if(Map[stopx][stopy]%2)Time=Map[stopx][stopy]/2+1;
    else Time=Map[stopx][stopy]/2;

    rec(stopx,stopy,fx,fy);

    fout<<Time<<" "<<fx<<" "<<fy;
}