Cod sursa(job #378841)

Utilizator alexandru92alexandru alexandru92 Data 29 decembrie 2009 19:08:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 29, 2009, 5:24 PM
 */
#include <queue>
#include <string>
#include <vector>
#include <utility>
#include <fstream>
#define pr pair< int, int >
#define mk make_pair< int, int >

/*
 *
 */
using namespace std;
string* S;
string::iterator it;
queue<int> X, Y;
const int dx[]={ -1, -1, -1, 0, 0, 1, 1, 1 }, dy[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
vector< pr > drum;
pr uz[120][120];
int main()
{bool ok=true, ok2=true;
 int n, m, i, j, rx, ry, jx, jy, x, y, xnew, ynew, s;
    ifstream in("rj.in");
    in>>n>>m;
    S=new string[n];
    in.ignore();
    for( i=0; i < n; ++i )
    {
        getline( in, S[i] );
        if( ok )
        {rx=i;
            ry=S[i].find( 'R' );
            if( ry >= 0 )
                ok=false;
        }
        if( ok2 )
        {jx=i;
            jy=S[i].find( 'J' );
            if( jy >= 0 )
                ok2=false;
        }
    }
    S[rx][ry]='X';
    uz[rx][ry]=mk( rx, ry );
    X.push(rx); Y.push(ry);
    while( !X.empty() && !ok )
    {
        x=X.front(); y=Y.front();
        X.pop(); Y.pop();
        for( i=0; i < 7; ++i )
        {
            xnew=x+dx[i];
            ynew=y+dy[i];
            if( xnew < 0 || ynew < 0 || xnew >= n || ynew >= n )
                continue;
            if( 'X' != S[xnew][ynew]  )
            {
                S[xnew][ynew]='X';
                uz[xnew][ynew]=mk( x, y );
                X.push(xnew); Y.push(ynew);
            }
            if( xnew == jx && ynew == jy )
            {
                ok=true;
                break;
            }
        }
    }
    do
    {
        drum.push_back( mk( jx, jy ) );
        x=jx;
        jx=uz[jx][jy].first;
        jy=uz[x][jy].second;
    }while( !( jx == rx && jy == ry ) );
    drum.push_back( mk( jx, jy ) );
    s=drum.size()/2;
    ofstream out("rj.out");
    out<<s<<' '<<(drum[s].first+1)<<' '<<(drum[s].second+1);
    delete[] S;
    return 0;
}