Cod sursa(job #1125722)

Utilizator IonSebastianIon Sebastian IonSebastian Data 26 februarie 2014 19:12:18
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int MAX_N = 100, MAX_M = 100;
const int dlin[] = {-1,-1,-1,0,0,1,1,1}, dcol[] = {-1,0,1,-1,1,-1,0,1};

struct poz {
    int lin;
    int col;
};

int n, m, ifin = 101, jfin = 101, fin = 1000000000, a[MAX_N+2][MAX_M+2];

bool gasit[MAX_N+2][MAX_M+2];

queue <poz> q;

void bordare(){
    int i, j;
    for(j = 0; j <= m+1; j++){
        a[0][j] = -1;
        a[n+1][j] = -1;
    }
    for(i = 0; i <= n+1; i++){
        a[i][0] = -1;
        a[i][m+1] = -1;
    }
}

void citire(){
    char c;
    int i = 1, j;
    poz p;
    for(j = 1; j <= m+1; j++){
        in.get(c);
        if(c == '\n' ){
            i++;
            if(i == n + 1)
                return;
            j = 0;
            continue;
        }
        if(c == 'X'){
            a[i][j] = -1;
        } else {
            if(c == 'R' || c == 'J'){
                a[i][j] = 1;
                if(c == 'J'){
                    gasit[i][j] = true;
                }
                p.lin = i;
                p.col = j;
                q.push(p);
            }
        }
    }
}

void lee(){
    poz x,y;
    int i;
    while(!q.empty()){
        x = q.front();
        q.pop();
        for(i = 0; i < 8; i++){
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if(a[y.lin][y.col] == 0){
                q.push(y);
                a[y.lin][y.col] = 1 + a[x.lin][x.col];
                gasit[y.lin][y.col] = gasit[x.lin][x.col];
            } else {
                if(a[y.lin][y.col] != -1){
                    if(gasit[y.lin][y.col] != gasit[x.lin][x.col] && a[x.lin][x.col]+1 == a[y.lin][y.col]){
                        if(a[x.lin][x.col] == fin){
                            if(y.lin < ifin){
                                ifin = y.lin;
                                jfin = y.col;
                                fin = a[y.lin][y.col];
                            } else if(y.lin == ifin && y.col < jfin){
                                ifin = y.lin;
                                jfin = y.col;
                                fin = a[y.lin][y.col];
                            }
                        } else if(a[y.lin][y.col] < fin){
                            ifin = y.lin;
                            jfin = y.col;
                            fin = a[y.lin][y.col];
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    char inutil;
    in >> n >> m;
    in.get(inutil);
    bordare();
    citire();
    lee();
    out << fin << " " << ifin << " " << jfin << "\n";
    return 0;
}