Cod sursa(job #2265733)

Utilizator AndoneAlexandruAndone Alexandru AndoneAlexandru Data 21 octombrie 2018 17:02:18
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

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

queue<pair<int, int> >q;

int rom[101][101]; // traseul lui romeo
int jul[101][101]; // traseul julietei
int linRomeo, colRomeo; // coordonatele lui Romeo
int linJulieta, colJulieta; // coordonatele Julietei

int di[] = {-1, -1, -1, 0, 1, 1, 1, 0}; // vector directie linie
int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1}; // vector directie coloana

void border(int n, int m, int a[101][101]) // bordare matrice cu -1
{
    for (int i = 0; i <= n+1; i++)
    {
        a[i][0] = -1;
        a[i][m+1] = -1;
    }
    for (int j = 0; j <= m+1; j++)
    {
        a[0][j] = -1;
        a[n+1][j] = -1;
    }
}

void citire(int n, int m) //citire si creeare matrice romeo & julieta
{
    for (int i = 1; i <= n; i++)
    {
        char x;
        for (int j = 1; j <= m; j++)
        {
            f.get(x); if (x == 10) break;
            if (x == ' ') {rom[i][j] = 0; jul[i][j] = 0;}
            else if (x == 'X') {rom[i][j] = -1; jul[i][j] = -1;}
            else if (x == 'R') {rom[i][j] = 0; jul[i][j] = 0; linRomeo = i; colRomeo = j;}
            else if (x == 'J') {rom[i][j] = 0; jul[i][j] = 0; linJulieta = i; colJulieta = j;}
        }
        if (x != 10) f.get();
    }
}

void leeRomeo()
{
    int x = linRomeo;
    int y = colRomeo;
    rom[x][y] = 1;
    q.push(make_pair(x, y));
    while(!q.empty())
    {
        pair<int, int>p = q.front();
        q.pop();
        for (int k = 0; k < 8; k++)
        {
            if(rom[p.first+di[k]][p.second+dj[k]] == 0)
            {
                rom[p.first+di[k]][p.second+dj[k]] = 1 + rom[p.first][p.second];
                q.push(make_pair(p.first+di[k], p.second+dj[k]));
            }
        }
    }
}

void leeJulieta()
{
    int x = linJulieta;
    int y = colJulieta;
    jul[x][y] = 1;
    q.push(make_pair(x, y));
    while(!q.empty())
    {
        pair<int, int>p = q.front();
        q.pop();
        for (int k = 0; k < 8; k++)
        {
            if(jul[p.first+di[k]][p.second+dj[k]] == 0)
            {
                jul[p.first+di[k]][p.second+dj[k]] = 1 + jul[p.first][p.second];
                q.push(make_pair(p.first+di[k], p.second+dj[k]));
            }
        }
    }
}

int main()
{
    int n, m;

    f >> n >> m; f.get();
    citire(n, m);

    border(n, m, rom);
    border(n, m, jul);

    leeRomeo();
    leeJulieta();

    int tmin = 200000, lin = 101, col = 101;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (rom[i][j] != -1 && rom[i][j] != 0)
                if (rom[i][j] == jul[i][j])
                    if (rom[i][j] < tmin)
                    {
                        tmin = rom[i][j];
                        lin = i;
                        col = j;
                    }

    g << tmin << ' ' << lin << ' ' << col;


//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//            g << rom[i][j] << ' ';
//        g << endl;
//    }
//    g << endl;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//            g << jul[i][j] << ' ';
//        g << endl;
//    }
//    g << endl;
//    g << linRomeo << ' ' << colRomeo << "   " << linJulieta << ' ' << colJulieta;
    return 0;
}