Cod sursa(job #1692933)

Utilizator leopop29Pop Leonard leopop29 Data 21 aprilie 2016 23:11:59
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#define NM 105
#define x first
#define y second
#define mp make_pair

using namespace std;

queue<pair<pair<int, int>, int>> q;
pair<int, int> p1, p2, cp;
char s[NM];
int mt[NM][NM], n, m;
int mn = 1<<30, mpx, mpy, cc;
int ox[] = {-1, -1, -1, 0, 1, 1, 1, 0},
    oy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

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


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

    f >> n >> m;
    f.getline(s, NM);
    for(int i = 1; i <= n; ++i)
    {
        f.getline(s, NM);
        for(int j = 1; j <= m; ++j)
            if(s[j-1] == 'X')
                mt[i][j] = -1;
            else if(s[j-1] == 'R')
                p1.x = i, p1.y = j, mt[i][j] = -1;
            else if(s[j-1] == 'J')
                p2.x = i, p2.y = j, mt[i][j] = -1;
    }

    q.push(mp(p1, 0));
    while(!q.empty())
    {
        cp.x = q.front().x.x;
        cp.y = q.front().x.y;
        cc = q.front().y;
        q.pop();

        if(!mt[cp.x][cp.y])
            mt[cp.x][cp.y] = cc;

        for(int i = 0; i < 8; ++i)
        {
            int a = cp.x+ox[i], b = cp.y+oy[i];
            if(inm(a, b) && mt[a][b] == 0)
                q.push(mp(mp(a, b), cc+1));
        }
        while(!q.empty() && mt[q.front().x.x][q.front().x.y])
            q.pop();
    }

    q.push(mp(p2, 0));
    while(!q.empty())
    {
        cp = q.front().x;
        cc = q.front().y;
        q.pop();

        if(cc == mt[cp.x][cp.y] && (cc < mn || (cc == mn && (mpx > cp.x || (mpx == cp.x && mpy > cp.y)))))
        {
            mn = cc;
            mpx = cp.x;
            mpy = cp.y;
        }

        mt[cp.x][cp.y] = -1;

        for(int i = 0; i < 8; ++i)
        {
            int a = cp.x+ox[i], b = cp.y+oy[i];
            if(inm(a, b) && mt[a][b] > 0)
                q.push(mp(mp(a, b), cc+1));
        }

        while(!q.empty() && mt[q.front().x.x][q.front().x.y] < 0)
            q.pop();
    }

    g << mn+1 << ' ' << mpx << ' ' << mpy;
}