Cod sursa(job #1580503)

Utilizator AndreiITCuriman Andrei AndreiIT Data 25 ianuarie 2016 21:36:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <queue>
#define POM -1
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
const int MAX = 105;
int n, m, xr, yr, xj, yj;
int dx[]={0,  0, 1, -1, 1,  1, -1, -1};
int dy[]={1, -1, 0,  0, 1, -1,  1, -1};
char mat[MAX][MAX];
int r[MAX][MAX];
int ju[MAX][MAX];
queue <pair<int, int> > q;
void lee(int v[][MAX], int x, int y)
{
    v[x][y] = 1;
    q.push({x, y});
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int d=0; d<8; ++d)
            if(v[ x+dx[d] ][ y+dy[d] ] == 0)
            {
                v[ x+dx[d] ][ y+dy[d] ] = v[x][y] + 1;
                q.push({x+dx[d], y+dy[d]});
            }
    }
}
void init()
{
    for(int i=0; i<=n+1; ++i)
        r[i][0] = r[i][m+1] = ju[i][0] = ju[i][m+1] = POM;
    for(int i=0; i<=m+1; ++i)
        r[0][i] = r[n+1][i] = ju[0][i] = ju[n+1][i] = POM;
}
int main()
{
    cin>>n>>m;
    cin.get();
    char ch[MAX];
    for(int i=1; i<=n; ++i)
    {
        cin.getline(ch, MAX);
        int p=0;
        for(int j=1; j<=m; ++j)
        {

            if(ch[p] == 'X')
            {
                r[i][j] = ju[i][j] = POM;
                p++;
                continue;
            }
            if(ch[p] == 'R')
            {
                xr = i;
                yr = j;
                p++;
                continue;
            }
            if(ch[p] == 'J')
            {
                xj = i;
                yj = j;
                p++;
                continue;
            }
            p++;
        }
    }
    init();
    lee(r, xr, yr);
    lee(ju, xj, yj);
    int sol = MAX*MAX, x, y;
//    for(int i=1; i<=n; ++i)
//    {
//        for(int j=1; j<=m; ++j)
//            cout<<r[i][j]<<' ';
//         cout<<'\n';
//    }
//    cout<<'\n';
//    for(int i=1; i<=n; ++i)
//    {
//        for(int j=1; j<=m; ++j)
//            cout<<ju[i][j]<<' ';
//         cout<<'\n';
//    }
//    cout<<'\n';
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(r[i][j] == ju[i][j] and r[i][j] > 0 and r[i][j] < sol)
            {
                sol = r[i][j];
                x = i;
                y = j;
            }
    cout<<sol<<' '<<x<<' '<<y;
    return 0;
}