Cod sursa(job #2094438)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 25 decembrie 2017 21:08:52
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <bits/stdc++.h>
using namespace std;

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

#define x first
#define y second

const int NMAX = 100;

struct RJ
{
    pair<int, int> pos;
    int val, dist;

    RJ(pair<int, int> _pos, int _val, int _dist) : pos(_pos), val(_val), dist(_dist) {}
}ans({NMAX, NMAX}, 0, NMAX * NMAX);

int n, m;
int a[NMAX + 2][NMAX + 2];
string str;

queue<RJ> q;
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1},
    dy[] = {1, 1, 0, -1, -1, -1, 0, 1};



void bordare();

int main()
{
    in >> n >> m; in.ignore();
    for(int i = 1; i <= n; i++)
    {
        getline(in, str);
        for(int j = 1; j <= m; j++)
            if(str[j - 1] == 'R' || str[j - 1] == 'J')
            {
                q.push(RJ({i, j}, (str[j - 1] == 'R' ? 1 : 2), 0));
                a[i][j] = (str[j - 1] == 'R' ? 1 : 2);
            }
            else if(str[j - 1] == 'X')
                a[i][j] = -1;
    }
    bordare();

    while(!q.empty())
    {
        RJ fr = q.front();

        for(int d = 0; d < 8; d++)
        {
            RJ vecin({fr.pos.x + dx[d], fr.pos.y + dy[d]}, fr.val, fr.dist + 1);
            if(a[vecin.pos.x][vecin.pos.y] == 0)
            {
                a[vecin.pos.x][vecin.pos.y] = vecin.val;
                q.push(vecin);
            }
            else if(a[vecin.pos.x][vecin.pos.y] != fr.val && !(a[vecin.pos.x][vecin.pos.y] == -1))
                if(vecin.dist + 1 < ans.dist)
                {
                    ans = vecin;
                    ans.dist++;
                }
                else if(vecin.dist + 1 == ans.dist && (ans.pos.x > vecin.pos.x || (ans.pos.x == vecin.pos.x && ans.pos.y > vecin.pos.y)))
                {
                    ans = vecin;
                    ans.dist++;
                }
        }

        q.pop();
    }

//    for(int i = 1; i <= n; i++)
//    {
//        for(int j = 1; j <= m; j++)
//            out << setw(2) << right << a[i][j] << ' ';
//        out << '\n';
//    }

    out << ans.dist << ' ' << ans.pos.x << ' ' << ans.pos.y << '\n';
    return 0;
}

void bordare()
{
    for(int i = 0; i <= n + 1; i++)
        a[i][0] = a[i][m + 1] = -1;
    for(int j = 0; j <= m + 1; j++)
        a[0][j] = a[n + 1][j] = -1;
}