Cod sursa(job #1051432)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 10 decembrie 2013 00:26:14
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <queue>
#define nmax 101
#define smax 9

using namespace std;

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

short n,m,i,j,k,h,a[nmax][nmax],v[smax],u[smax],b[nmax][nmax],minim=nmax*nmax;
string s;

queue <short> qri,qrj,qji,qjj;

void ini(){
    v[1]=-1; u[1]=-1;
    v[2]=-1; u[2]=1;
    v[3]=-1; u[3]=0;
    v[4]=1; u[4]=0;
    v[5]=1; u[5]=-1;
    v[6]=1; u[6]=1;
    v[7]=0; u[7]=1;
    v[8]=0; u[8]=-1;
}

void romeo(){
    
    while (!qri.empty()){
        
        i=qri.front(), j=qrj.front();
        qri.pop(), qrj.pop();
        
        k=a[i][j];
        
        for (h=1; h<=8; h++)
            if (a[i+v[h]][j+u[h]]==-1) a[i+v[h]][j+u[h]]=k+1, qri.push(i+v[h]), qrj.push(j+u[h]);
        
    }
    
}

void juliet(){
    
    while (!qji.empty()){
        
        i=qji.front(), j=qjj.front();
        qji.pop(), qjj.pop();
        
        k=b[i][j];
        
        for (h=1; h<=8; h++)
            if (b[i+v[h]][j+u[h]]==-1 ) b[i+v[h]][j+u[h]]=k+1, qji.push(i+v[h]), qjj.push(j+u[h]);
        
    }
    
}

int main(){
    
    ini();
    
    in >> n >> m;
    in.get();
    
    for (i=1; i<=n; i++){
        getline(in, s);
        k=0;
        for (j=0; j<m; j++){
            k++;
            if (s[j]=='R') qri.push(i), qrj.push(k), a[i][k]=1, b[i][k]=-1;
            else if (s[j]=='J') qji.push(i), qjj.push(k), b[i][k]=1, a[i][k]=-1;
            else if (s[j]=='X') a[i][k]=-2, b[i][k]=-2;
            else a[i][k]=-1, b[i][k]=-1;
        
            if (a[i][k]==0) a[i][k]=-1, b[i][k]=-1;
            
        }
    }
    
    romeo();
    
    juliet();
    
    h=nmax, k=nmax;
    
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (a[i][j]==b[i][j] && (a[i][j]!=-2 && a[i][j]!=-1)){
                if (a[i][j]<=minim){
                    if (a[i][j]==minim){
                        if (j<k) k=j;
                    } else minim=a[i][j], h=i, k=j;
                }
            }
    
    out << minim << " " << h << " " << k;
    
    return 0;
        
}