Cod sursa(job #1927225)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 14 martie 2017 23:45:51
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <string>
#include <queue>
#include <climits>
#define DM 100
using namespace std;

ifstream fi ("rj.in");
ofstream fo ("rj.out");
int d[DM][DM], t[DM][DM];
string s;
int n, m, mn = INT_MAX, ri, rj, ji, jj, vi[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, vj[8] = {0, 1, 1, 1, 0, -1, -1, -1}, a, b;
queue <pair <int, int> > q;

int main ()
{
    fi >> n >> m;
    getline(fi, s);
    for (int i = 0; i < n; ++i)
    {
        getline(fi, s);
        for (int j = 0; j < m; ++j)
            if (s[j] != ' ')
            {
                t[i][j] = -1, d[i][j] = -1;
                if (s[j] == 'R')
                    ri = i, rj = j, t[i][j]+=2;
                if (s[j] == 'J')
                    ji = i, jj = j, d[i][j]+=2;
            }
    }
    q.push(make_pair(ri, rj));
    while (!q.empty())
    {
        a = q.front().first, b = q.front().second;
        for (int i = 0; i < 8; ++i)
            if (t[a+vi[i]][b+vj[i]] == 0 && a + vi[i] < n && a + vi[i] >= 0 && b + vj[i] < m && b + vj[i] >= 0)
            {
                q.push(make_pair(a + vi[i], b + vj[i]));
                t[a+vi[i]][b+vj[i]] = t[a][b] + 1;
            }
        q.pop();
    }
    q.push(make_pair(ji, jj));
    while (!q.empty())
    {
        a = q.front().first, b = q.front().second;
        for (int i = 0; i < 8; ++i)
            if (d[a+vi[i]][b+vj[i]] == 0 && a + vi[i] < n && a + vi[i] >= 0 && b + vj[i] < m && b + vj[i] >= 0)
            {
                q.push(make_pair(a + vi[i], b + vj[i]));
                d[a+vi[i]][b+vj[i]] = d[a][b] + 1;
            }
        q.pop();
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (d[i][j] == t[i][j] && d[i][j] > 0 && d[i][j] < mn)
                mn = d[i][j], a = i + 1, b = j + 1;
    fo << mn << ' ' << a << ' ' << b;
    return 0;
}