Cod sursa(job #2781564)

Utilizator Stefan_GhinescuGhinescu Stefan-George Stefan_Ghinescu Data 9 octombrie 2021 20:17:20
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.74 kb
#if 0

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int a[105][105], n, m, nrMarcei;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

///ifstream fin("insule.in");
///ofstream fout("insule.out");

struct poz
{
    int x, y;
    poz(int x, int y)
        :x(x), y(y)
    {

    }
};

bool inside(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

void showCh()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == -1)
            {
                cout << '#';
            }
            else if (a[i][j] == 0)
            {
                cout << '.';
            }
            else if (a[i][j] == 1)
            {
                cout << 'M';
            }
            else if (a[i][j] == -2)
            {
                cout << '@';
            }
            cout << ' ';
        }
        cout << '\n';
    }
}

void show()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == -1)
            {
                cout << '#';
            }
            else if (a[i][j] == -2)
            {
                cout << '@';
            }
            else
            {
                cout << a[i][j];
            }
            cout << ' ';
        }
        cout << '\n';
    }
}

int lee2(queue <poz>q)
{
    while (!q.empty())
    {
        int ii = q.front().x;
        int jj = q.front().y;
        for (int k = 0; k < 4; ++k)
        {
            int iii = ii + dx[k];
            int jjj = jj + dy[k];
            if (inside(iii, jjj))
            {
                if (a[iii][jjj] == 0)
                {
                    a[iii][jjj] = a[ii][jj] + 1;
                    q.push(poz(iii, jjj));
                }
                else if (a[iii][jjj] == 1)
                {
                    --nrMarcei;
                    q.push(poz(iii, jjj));
                }
            }
        }
        q.pop();
    }
    return 0;
}

/**

##########
#M.#....M#
#M.#.....#
#.#......#
##......M#
#........#
#..M....##
#....M.#M#
##########

*/

int main()
{
    queue <poz> q;
    int t, i, j;
    char ch;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        nrMarcei = 0;
        for (i = 0; i < n; ++i)
        {
            for (j = 0; j < m; ++j)
            {
                cin >> ch;
                if (ch == '#')
                    a[i][j] = -1;
                else if (ch == '.')
                    a[i][j] = 0;
                else if (ch == 'M')
                {
                    a[i][j] = 1;
                    ++nrMarcei;
                    q.push(poz(i, j));
                }
            }
        }
        lee2(q);
        show();
    }
    return 0;
}

#endif // 0

#include <iostream>
#include <cstring>
#include <fstream>
#include <queue>

using namespace std;

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

int dx[] = {-1, -1, 0, 1, 1,  1,  0, -1};
int dy[] = { 0,  1, 1, 1, 0, -1, -1, -1};

int n, m;

struct idk
{
    int val, drum;
};

idk a[105][105];

struct Vec2
{
    int x, y;
};

bool inb(int a, int b)
{
    return 0 <= a && a < n && 0 <= b && b < m;
}

void show()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cout << a[i][j].val << ' ';
        }
        cout << '\n';
    }
}

Vec2 lee(queue <Vec2>& q)
{
    int x, y, xx, yy, xfin = -1, yfin = -1;
    bool ok = 0;
    while (!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        for (int k = 0; k < 8; ++k)
        {
            xx = x + dx[k];
            yy = y + dy[k];
            if (inb(xx, yy))
            {
                if (a[xx][yy].val == 0 && a[xx][yy].drum == 0)
                {
                    a[xx][yy].val = a[x][y].val + 1;
                    a[xx][yy].drum = a[x][y].drum;
                    q.push({xx, yy});
                }
                if (a[xx][yy].val == a[x][y].val + 1 && a[xx][yy].drum == -1 * a[x][y].drum && ok == 0)
                {
                    ok = 1;
                    xfin = xx;
                    yfin = yy;
                }
                if (a[xx][yy].val == a[x][y].val + 1 && a[xx][yy].drum == -1 * a[x][y].drum && a[xx][yy].val == a[xfin][yfin].val && yy < yfin)
                {
                    xfin = xx;
                    yfin = yy;
                }
            }
        }
        q.pop();
    }
    return {xfin, yfin};
}

int main()
{
    queue <Vec2> q;
    int i, j;
    char ch[101];
    fin >> n >> m;
    fin.get();
    for (i = 0; i < n; ++i)
    {
        fin.getline(ch, m + 1);
        for (j = 0; j < m; ++j)
        {
            if (ch[j] == 'X')
            {
                a[i][j] = {-1, 0};
            }
            else if (ch[j] == ' ')
            {
                a[i][j] = {0, 0};
            }
            else if (ch[j] == 'R')
            {
                a[i][j] = {1, 1};
                q.push({i, j});
            }
            else if (ch[j] == 'J')
            {
                a[i][j] = {1, -1};
                q.push({i, j});
            }
        }
    }
    Vec2 v = lee(q);
    fout << a[v.x][v.y].val << ' ' << v.x + 1 << ' ' << v.y + 1;
    return 0;
}


/**
T:
    Campion:    impozit, sqr, fib, descfib, ech
    Infoarena:  next
    pbinfo:     pilula

    Campion:    radical, sumb, pm, numar4, doctor, munte1, dale

    PbInfo:     #287, #290, #292, #505, #1321
    UVA:        465, 619, 748, 10083, 10523

    UVA:        11849, 501
    PbInfo:     roata
*/