Cod sursa(job #2343280)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 13 februarie 2019 20:52:57
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <queue>
#include <string>
#include <fstream>
#include <iostream>
#define inf 0x3f3f3f3f
#define x first
#define y second
#define len 101

using namespace std;

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

typedef pair<unsigned, unsigned> p;

queue<p> q;

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

p start, finish, inter;

unsigned N, M;
int matr[len][len];

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

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