Cod sursa(job #850613)

Utilizator stoicatheoFlirk Navok stoicatheo Data 8 ianuarie 2013 17:26:28
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <queue>
#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream in ("rj.in");
ofstream out ("rj.out");
 
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
 
int A[200][200];
int B[200][200];
char S[110];
 
int main ()
{   
    int N, M;
    int i, j;
    int Rx, Ry;
    int Jx, Jy;
    int nowx, nowy;
    int vx, vy;
    int minn, xmin, ymin;
    char c;
     
    queue < pair < int, int > > Q;
    pair < int, int > now;
     
    //scanf ("%d %d\n", &N, &M);
    in >> N >> M;
    //in.ignore ();
     
    for (i = 0; i <= M + 1; i ++){
        A[0][i] = -1;
        A[N + 1][i] = -1;
        B[0][i] = -1;
        B[N + 1][i] = -1;
    }
     
    for (i = 0; i <= N + 1; i ++){
        A[i][0] = -1;
        A[i][M + 1] = -1;
        B[i][0] = -1;
        B[i][M + 1] = -1;
    }
     
    /*for (i = 0; i <= N + 1; i ++){
        for (j = 0; j <= M + 1; j ++)
            cout << A[i][j] << " ";
         
        cout << "\n";
    }*/
     
    for (i = 1; i <= N; i ++){
        in.get ();
        in.get (S, 105);
        //in.getline (S, 105);
         
        for (j = 0; j < M; j ++){
            c = S[j];
             
            if (c == 'R'){
                A[i][j + 1] = 1;
                B[i][j + 1] = -1;
                Rx = i;
                Ry = j + 1;
            }
             
            if (c == 'J'){
                B[i][j + 1] = 1;
                A[i][j + 1] = -1;
                Jx = i;
                Jy = j + 1;
            }
             
            if (c == 'X'){
                A[i][j + 1] = -1;
                B[i][j + 1] = -1;
            }
        }
    }
     
    /*for (i = 0; i <= N + 1; i ++){
        for (j = 0; j <= M + 1; j ++)
            cout << A[i][j] << " ";
         
        cout << "\n";
    }*/
     
    //cout << "\n" << Rx << " " << Ry << "\n" << Jx << " " << Jy;
         
    Q.push (make_pair (Rx, Ry));
     
    while (!Q.empty ()){
        now = Q.front ();
        Q.pop ();
        nowx = now.first;
        nowy = now.second;
         
        for (i = 0; i < 8; i ++){
            vx = nowx + dx[i];
            vy = nowy + dy[i];
             
            if (A[vx][vy] == -1)
                continue;
             
            if ((!A[vx][vy]) || (A[vx][vy] > A[nowx][nowy] + 1)){
                A[vx][vy] = A[nowx][nowy] + 1;
                Q.push (make_pair (vx, vy));
            }
        }
    }
     
    Q.push (make_pair (Jx, Jy));
     
    while (!Q.empty ()){
        now = Q.front ();
        Q.pop ();
        nowx = now.first;
        nowy = now.second;
         
        for (i = 0; i < 8; i ++){
            vx = nowx + dx[i];
            vy = nowy + dy[i];
             
            if (B[vx][vy] == -1)
                continue;
             
            if ((!B[vx][vy]) || (B[vx][vy] > B[nowx][nowy] + 1)){
                B[vx][vy] = B[nowx][nowy] + 1;
                Q.push (make_pair (vx, vy));
            }
             
            /*if (A[vx][vy] == B[vx][vy]){
                out << A[vx][vy] << " " << vx << " " << vy;
                 
                return 0;
            }*/
        }
    }
     
    minn = (1 << 30);
    for (i = 1; i <= N; i ++)
        for (j = 1; j <= M; j ++)
            if (A[i][j] && A[i][j] != -1 && A[i][j] == B[i][j] && A[i][j] < minn){
                //out << A[i][j] << " " << i << " " << j;
                minn = A[i][j];
                xmin = i;
                ymin = j;
            }
             
    out << minn << " " << xmin << " " << ymin;
         
    return 0;
}