Cod sursa(job #1050621)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 8 decembrie 2013 20:41:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#define nmax 101

using namespace std;

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

short n,m,i,j,k,minimi=nmax,minimj=nmax,valmin=2*nmax;
short a[nmax][nmax];
char x;
queue <short> qi,qj;

void minimum(short x, short y, short z){

    if (a[x][y]==z && z<=valmin){
            if (x<=minimi){
                if (x==minimi){
                    if (y<minimj) minimj=y, valmin=a[minimi][minimj];
                } else minimi=x, minimj=y, valmin=a[minimi][minimj];
            }
    }
    
}

void rj(){
    
    while (!qi.empty()){
        
        i=qi.front(), j=qj.front();
        
        qi.pop(), qj.pop();
        
        int k=a[i][j];
        
        if (a[i-1][j-1]==-1 || a[i-1][j-1]>k)
            minimum(i-1,j-1,k+1), a[i-1][j-1]=k+1, qi.push(i-1), qj.push(j-1);
        
        if (a[i-1][j]==-1 || a[i-1][j]>k)
            minimum(i-1,j,k+1), a[i-1][j]=k+1, qi.push(i-1), qj.push(j);
        
        if (a[i-1][j+1]==-1 || a[i-1][j+1]>k)
            minimum(i-1,j+1,k+1), a[i-1][j+1]=k+1, qi.push(i-1), qj.push(j+1);
            
        if (a[i][j-1]==-1 || a[i][j-1]>k)
            minimum(i,j-1,k+1), a[i][j-1]=k+1, qi.push(i), qj.push(j-1);
            
        if (a[i][j+1]==-1 || a[i][j+1]>k)
            minimum(i,j+1,k+1), a[i][j+1]=k+1, qi.push(i), qj.push(j+1);
        
        if (a[i+1][j-1]==-1 || a[i+1][j-1]>k)
            minimum(i+1,j-1,k+1), a[i+1][j-1]=k+1, qi.push(i+1), qj.push(j-1);
    
        if (a[i+1][j]==-1 || a[i+1][j]>k)
            minimum(i+1,j,k+1), a[i+1][j]=k+1, qi.push(i+1), qj.push(j);
        
        if (a[i+1][j+1]==-1 || a[i+1][j+1]>k)
            minimum(i+1,j+1,k+1), a[i+1][j+1]=k+1, qi.push(i+1), qj.push(j+1);
        
    }
    
}

void read(){

    in >> n >> m;
    
    for (i=1; i<=n; i++){
        in.get();
        for (j=1; j<=m; j++){
            
            in.get(x);
            
            if (x=='R') a[i][j]=1, qi.push(i), qj.push(j);
            else if (x=='J') a[i][j]=1, qi.push(i), qj.push(j);
            
            if (isspace(x)) a[i][j]=-1;
            
            if (x=='X') a[i][j]=-2;
            
        }
    }
    
}

int main(){
    
    read();
    
    rj();
    
    out<<valmin<<" "<<minimi<<" "<<minimj<<"\n";
    
    return 0;
}