Cod sursa(job #2345226)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 16 februarie 2019 00:03:49
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <queue>
#include <string>
#include <fstream>
#define x first
#define y second
#define len 101

using namespace std;

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

typedef pair<int, int> p;

queue<p> q;

int const diri[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dirj[] = {-1, 0, 1, -1, 1, -1, 0, 1}, inf = 0x3f3f3f3f;

p start, finish;

int N, M, rmat[len][len], jmat[len][len];

bool inside(int l, int c)
{
    return l >= 1 && l <= N && c >= 1 && c <= M;
}

int main()
{
    in >> N >> M;
    in.get();
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            rmat[i][j] = jmat[i][j] = inf;
    for(int i = 1; i <= N; ++i)
    {
        string s;
        getline(in, s);
        for(int j = 1; j <= M; ++j)
        {
            if(s[j - 1] == 'X')
                rmat[i][j] = jmat[i][j] = -1;
            else if(s[j - 1] == 'R')
            {
                start.x = i;
                start.y = j;
                rmat[i][j] = 1;
                q.push({i, j});
            }
            else if(s[j - 1] == 'J')
            {
                finish.x = i;
                finish.y = j;
            }
        }
    }
    while(!q.empty())
    {
        int i = q.front().x, j = q.front().y;
        q.pop();
        for(int k = 0; k < 8; ++k)
        {
            int ii = i + diri[k], jj = j + dirj[k];
            if(inside(ii, jj) && rmat[ii][jj] != -1 && rmat[ii][jj] > rmat[i][j] + 1)
            {
                rmat[ii][jj] = rmat[i][j] + 1;
                q.push({ii, jj});
            }
        }
    }
    jmat[finish.x][finish.y] = 1;
    q.push({finish.x, finish.y});
    while(!q.empty())
    {
        int i = q.front().x, j = q.front().y;
        q.pop();
        for(int k = 0; k < 8; ++k)
        {
            int ii = i + diri[k], jj = j + dirj[k];
            if(inside(ii, jj) && jmat[ii][jj] != -1 && jmat[ii][jj] > jmat[i][j] + 1)
            {
                jmat[ii][jj] = jmat[i][j] + 1;
                q.push({ii, jj});
            }
        }
    }
    int dist = rmat[finish.x][finish.y], mij = dist / 2 + dist % 2;
    out << mij << ' ';
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(dist % 2 && rmat[i][j] == mij && jmat[i][j] == mij)
            {
                out << i << ' ' << j;
                return 0;
            }
            else if(!(dist % 2) && rmat[i][j] == mij && jmat[i][j] == mij + 1)
            {
                out << i << ' ' << j;
                return 0;
            }
}