Cod sursa(job #643384)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 3 decembrie 2011 16:42:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("rj.in"); ofstream g("rj.out");
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
char a[101][101];
char x;
int solR[101][101],solJ[101][101];
int n,m,i,j,xfR,yfR,xx,yy,xfJ,yfJ;
pair<int,int> romeo;
int main(){
        deque < pair<int,int> > Q;
        f>>n>>m;
        f.get();
        for ( i = 1; i <= n; i++ ){
                for ( j = 1; j <= m; j++ ){
                                x=f.get();
                                a[i][j]=x;
                                pair <int,int> romeo;
                                romeo.first=i;
                                romeo.second=j;
                                if ( a[i][j] == 'R' ) Q.push_back(romeo),solR[i][j]=1;
                                if ( a[i][j] == 'J' ) {xfR=i; yfR=j;}
                }
                f.get();
        }
        for (;!Q.empty();Q.pop_front()){
                pair <int,int> ret=Q.front();
                for (int k = 0; k < 8; k++ ){
                        pair <int,int> acm=ret;
                        acm.first=acm.first+dx[k];
                        acm.second=acm.second+dy[k];
                        if(acm.first >= 1 && acm.first <= n && acm.second >= 1 && acm.second <= m && a[acm.first][acm.second]!='X'){
                                if(!solR[acm.first][acm.second]){
                                        solR[acm.first][acm.second]=solR[ret.first][ret.second]+1;
                                        Q.push_back(acm);
                                }
                        }
        }
        }
        for ( i = 1; i <= n; i++ ){
                for ( j = 1; j <= m; j++ ){
                        pair<int,int> julieta;
                        julieta.first=i;
                        julieta.second=j;
                        if ( a[i][j] == 'J' ) Q.push_back(julieta),solJ[i][j]=1;
                        if ( a[i][j] == 'R' ) {xfJ=i; yfJ=j;}
                }
        }
        for (;!Q.empty();Q.pop_front()){
                pair <int,int> ret=Q.front();
                for (int k = 0; k < 8; k++ ){
                        pair <int,int> acm=ret;
                        acm.first=acm.first+dx[k];
                        acm.second=acm.second+dy[k];
                        if(acm.first >= 1 && acm.first <= n && acm.second >= 1 && acm.second <= m && a[acm.first][acm.second]!='X'){
                                if(!solJ[acm.first][acm.second]){
                                        solJ[acm.first][acm.second]=solJ[ret.first][ret.second]+1;
                                        Q.push_back(acm);
                                }
                        }
        }
        }
        for(int i=1;i<=n;++i)
                for(int j=1;j<=m;++j)
                {
                        if(solR[i][j]==0) solR[i][j]=2000000000;
                        if(solJ[i][j]==0) solJ[i][j]=2000000000;
                }
 
    int mn=2000000000;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            mn = min(mn, max(solJ[i][j],solR[i][j]));
    g<<mn;
    for(int i=1;i<=n;++i)
         for(int j=1;j<=m;++j)
             if(max(solJ[i][j],solR[i][j])==mn)
             {
                  g<<' ' <<i << ' '<<j<<'\n';
                  return 0;
             }
 
    return 0;
}