Cod sursa(job #1119320)

Utilizator abel1090Abel Putovits abel1090 Data 24 februarie 2014 16:57:55
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.41 kb
///RJ
#include<fstream>
#include<vector>
#include<utility>
#include<queue>
#include<limits>
#include<string>

using namespace std;

typedef pair<short, short> PSHORT;

struct COORD
{
   short x;
   short y;
};

short map[5][5];///vector< vector<short> > map;
queue<PSHORT> q;
COORD result_coord;
short result_time=numeric_limits<short>::max();

bool ok(short x, short y)
{
   if(map[y][x]==-1)
       return false;
   else
       if(map[y][x]<map[q.front().second][q.front().first]+1)
           return false;
       else
           return true;
}

bool found(short x,short y)
{
   if(map[y][x]==map[q.front().second][q.front().first]+1 && result_time>map[q.front().second][q.front().first]+1)
       return true;
   else
       return false;
}

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

    short N, M; ///m-sor
    string test;

    fin>>M>>N;
    fin.get();

    ///map.resize(M);
    ///for(short i=0; i<M; i++)
        ///map[i].resize(N);

    for(short i=0; i<M; i++)
    {
        getline(fin, test);
        for(short j=0; j<N; j++)
            switch(test[j])
            {
                case ' ': map[i][j]=numeric_limits<short>::max(); break;
                case 'R': map[i][j]=0; q.push(PSHORT(j, i)); break;
                case 'J': map[i][j]=0; q.push(PSHORT(j, i)); break;
                case 'X': map[i][j]=-1; break;
            }
    }

    short x_temp, y_temp;

    while(!q.empty())
    {
        x_temp=q.front().first+1;
        y_temp=q.front().second;

        if(x_temp<N && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first+1;
        y_temp=q.front().second-1;

        if(x_temp<N && y_temp>=0 && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first;
        y_temp=q.front().second-1;

        if(y_temp>=0 && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first-1;
        y_temp=q.front().second-1;

        if(x_temp>=0 && y_temp>=0 && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first-1;
        y_temp=q.front().second;

        if(x_temp>=0 && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first-1;
        y_temp=q.front().second+1;

        if(x_temp>=0 && y_temp<M && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first;
        y_temp=q.front().second+1;

        if(x_temp<M && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        x_temp=q.front().first+1;
        y_temp=q.front().second+1;

        if(x_temp<N && y_temp<M && ok(x_temp, y_temp))
        {
            if(found(x_temp, y_temp))
            {
                result_coord.x=x_temp;
                result_coord.y=y_temp;
                result_time=map[q.front().second][q.front().first]+1;
            }
            map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
            q.push(PSHORT(x_temp, y_temp));
        }

        q.pop();
    }

    fout<<result_time+1<<' '<<result_coord.y+1<<' '<<result_coord.x+1<<'\n';

    return 0;
}