Cod sursa(job #2698489)

Utilizator dragostanTantaru Dragos Constantin dragostan Data 22 ianuarie 2021 11:55:11
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

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

const size_t MAXN = 101, MAXM = 101;
int oras[MAXN][MAXM], r[MAXN][MAXM], jul[MAXN][MAXM]; // in d e distanta pana la cel mai apropiat 1
const int dx[] = {1, 1, 0, -1, -1, -1,  0,   1};
const int dy[] = {0, 1, 1,  1,  0, -1, -1, -1};
int n, m;
int ri, rj, ji, jj;


void parcurge(int i, int j, int (*dist)[MAXM]);
void check();
int main()
{
    in >> n >> m;
    char dummy[MAXM];
    in.getline(dummy, MAXM);
    /*
     -100 = inpasabil
     0 = se poate trece\romeo\julieta
    */
    for(int i = 1; i <= n; ++i)
    {
        char linie[MAXM];
        in.getline(linie, (size_t)(m+1) * sizeof(char));
        for(int j = 0; j < m; ++j)
        {
            if(linie[j] == 'R')
            {
                ri = i;
                rj = j + 1;
                oras[i][j + 1] = 0;
            }
            else if(linie[j] == 'J')
            {
                ji = i;
                jj = j + 1;
                oras[i][j + 1] = 0;
            }
            else if(linie[j] == ' ')
            {
                oras[i][j + 1] = 0;
            }
            else if(linie[j] == 'X')
            {
                oras[i][j + 1] = -100;
            }
        }
    }

    parcurge(ri, rj, r);
    parcurge(ji, jj, jul);
    check();
	return 0;
}

void parcurge(int si, int sj, int (*dist)[MAXM])
{
    queue<pair<int, int>> coada;
    coada.push({si, sj});
    dist[si][sj] = 1;

    while(!coada.empty())
    {
        pair<int, int> cur = coada.front();
        coada.pop();

        for(int i = 0; i < 8; ++i)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx > 0 && ny > 0 && nx <= n && ny <= m)
            {
                if(oras[nx][ny] == 0 && dist[nx][ny] == 0)
                {
                    dist[nx][ny] = dist[cur.first][cur.second] + 1;
                    coada.push({nx, ny});
                }
            }
        }
    }
}

void check()
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(r[i][j] > 0 && r[i][j] == jul[i][j])
            {
                out<< r[i][j] << ' ' << i << ' ' << j;
                i = n + 1;
                j = m + 1; // break conditions
            }
        }
    }
}