Cod sursa(job #1087158)

Utilizator Athena99Anghel Anca Athena99 Data 18 ianuarie 2014 23:34:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <queue>
#include <string>

using namespace std;

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

const int inf= 1<<30;
const int dx[]= {1, 0, -1, 0, -1, -1, 1, 1};
const int dy[]= {0, 1, 0, -1, -1, 1, -1, 1};
const int nmax= 100;
const int mmax= 100;

struct str {
    int x, y;
};

inline str mp( int x, int y ) {
    str sol;
    sol.x= x;
    sol.y= y;
    return sol;
}

int dr[nmax+2][mmax+2], dj[nmax+2][mmax+2];

void bfs( int a[][mmax+2], int x, int y ) {
    queue <str> q;
   
    q.push( mp( x, y ) );
    while ( !q.empty() ) {
        int xb= q.front().x, yb= q.front().y;
        q.pop();
        
        for ( int i= 0; i<8; ++i ) {
            int x= dx[i], y= dy[i];
            if ( a[xb+x][yb+y]==inf ) {
                a[xb+x][yb+y]= a[xb][yb]+1;
                q.push( mp( xb+x, yb+y ) );
            }
        }
    }
}

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 0; i<=n+1; ++i ) {
        dr[i][0]= dj[i][0]= dr[i][m+1]= dj[i][m+1]= -1;
    }
    for ( int j= 0; j<=m+1; ++j ) {
        dr[0][j]= dj[0][j]= dr[n+1][j]= dj[n+1][j]= -1;
    }

    string x;
    getline( fin, x );
    int xr= 0, yr= 0, xj= 0, yj= 0;
    for ( int i= 1; i<=n; ++i ) {
        getline( fin, x );
        for ( int j= 1; j<=m; ++j ) {
            if ( x[j-1]==' ' ) {
                dr[i][j]= dj[i][j]= inf;
            } else if ( x[j-1]=='X' ) {
                dr[i][j]= dj[i][j]= -1;
            } else if ( x[j-1]=='R' ) {
                dj[i][j]= inf;
                xr= i, yr= j;
            } else if ( x[j-1]=='J' ) {
                dr[i][j]= inf;
                xj= i, yj= j;
            }
        }
    }

    bfs( dr, xr, yr );
    bfs( dj, xj, yj );

    int sol= 0, solx= 0, soly= 0, min= inf;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            if ( dr[i][j]==dj[i][j] && dr[i][j]<min && dr[i][j]>=0 && dr[i][j]!=inf ) {
                min= sol= dr[i][j];
                solx= i, soly= j;
            }
        }
    }

    fout<<sol<<" "<<solx<<" "<<soly<<"\n";

    return 0;
}