Cod sursa(job #1499089)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 10 octombrie 2015 09:54:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

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

const int maxn = 105;
const int inf = (1 << 30);
int ro[maxn][maxn];
int ju[maxn][maxn];
int M[maxn][maxn];
char linie[maxn];

queue < pair <int, int> > q1;
queue < pair <int, int> > q2;

int dx[] = {-1,-1, -1, 1, 1, 1, 0, 0};
int dy[] = { 0, 1, -1, 0, 1,-1, 1,-1};

int inside(int x, int y, int n, int m)
{
    if(x <= 0 || y <= 0 || x > n || y > m)
        return 0;
    return 1;
}

void lee_R(int n, int m, pair <int, int> xstart)
{
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            ro[i][j] = inf;
    q1.push(xstart);
    ro[xstart.first][xstart.second] = 1;
    while(!q1.empty())
    {
        pair <int, int> p = q1.front();
        q1.pop();
        int x = p.first;
        int y = p.second;
        for(int i = 0 ; i < 8; i++)
        {
            int xnou = x + dx[i];
            int ynou = y + dy[i];
            if(ro[xnou][ynou] > ro[x][y] + 1 && inside(xnou, ynou, n, m) && M[xnou][ynou] != -1) {
                ro[xnou][ynou] = ro[x][y] + 1;
                q1.push(make_pair(xnou, ynou));
            }
        }
    }
}

void lee_J(int n, int m, pair <int, int> ystart)
{
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            ju[i][j] = inf;
    q2.push(ystart);
    ju[ystart.first][ystart.second] = 1;
    while(!q2.empty())
    {
        pair <int, int> p = q2.front();
        q2.pop();
        int x = p.first;
        int y = p.second;
        for(int i = 0 ; i < 8; i++)
        {
            int xnou = x + dx[i];
            int ynou = y + dy[i];
            if(ju[xnou][ynou] > ju[x][y] + 1 && inside(xnou, ynou, n, m) && M[xnou][ynou] != -1) {
                ju[xnou][ynou] = ju[x][y] + 1;
                q2.push(make_pair(xnou, ynou));
            }
        }
    }
}
int main()
{
    int n, m;
    in >> n >> m;
    pair <int, int> xstart;
    pair <int, int> ystart;
    in.getline(linie + 1, maxn);
    for (int i = 1; i <= n; ++i) {
        in.getline(linie + 1, maxn);
        for(int j = 1; j <= m; j++)
        {
            char x;
            x = linie[j];
            if(x == 'X')
                M[i][j] = -1;
            if(x == 'R')
                xstart = make_pair(i, j);
            if(x == 'J')
                ystart = make_pair(i, j);
        }
    }

    lee_R(n, m, xstart);
    lee_J(n, m, ystart);

    int mn = inf;
    pair <int, int> pct;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(mn > ro[i][j] && ro[i][j] == ju[i][j])
            {
                mn = ro[i][j];
                pct = make_pair(i, j);
            }
        }
    }
    out << mn << " " << pct.first << " " << pct.second << "\n";
    return 0;
}