Cod sursa(job #1328126)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 28 ianuarie 2015 01:18:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int INF = 1e9;
const int NMax = 105;
const int dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
const int dy[] = {1, 0, -1, 0, -1, 1, 1, -1};
int R[NMax][NMax],J[NMax][NMax];
deque <int> qx,qy;

void afisare(int n, int m){
    int x,y;
    int tmin = INF;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(R[i][j] == J[i][j] && R[i][j] != -1){
                if(tmin > R[i][j] && R[i][j] != 0){
                    tmin = R[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    g << tmin << " " << x << " " << y;
}

void lee(){
    int x,y,nx,ny;
    while(!qx.empty()){
        x = qx.front();
        y = qy.front();
        qx.pop_front();
        qy.pop_front();
        for(int i = 0; i < 8; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(R[nx][ny] == 0){
                R[nx][ny] = R[x][y] + 1;
                qx.push_back(nx);
                qy.push_back(ny);
            }
        }
    }
}

void lee1(){
    int x,y,nx,ny;
    while(!qx.empty()){
        x = qx.front();
        y = qy.front();
        qx.pop_front();
        qy.pop_front();
        for(int i = 0; i < 8; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(J[nx][ny] == 0){
                J[nx][ny] = J[x][y] + 1;
                qx.push_back(nx);
                qy.push_back(ny);
            }
        }
    }
}

int main()
{
    int N,M,xr,yr,xj,yj;
    char o;
    f >> N >> M;
    f.get(o);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M + 1; j++){
            f.get(o);
            if(o == 'X')
                R[i][j] = J[i][j] = -1;
            if(o == 'R'){
                xr = i;
                yr = j;
                R[xr][yr] = 1;
            }
            if(o == 'J'){
                xj = i;
                yj = j;
                J[xj][yj] = 1;
            }
            if(o == '\n')
                j = INF;
        }
    }
    for(int i = 0; i <= M + 1; i++)
        R[0][i] = R[N+1][i] = J[0][i] = J[N+1][i] = -1;
    for(int i = 0; i <= N + 1; i++)
        R[i][0] = R[i][M+1] = J[i][0] = J[i][M+1] = -1;
    qx.push_back(xr);
    qy.push_back(yr);
    lee();
    qx.push_back(xj);
    qy.push_back(yj);
    lee1();
    afisare(N,M);
    return 0;
}