Cod sursa(job #1692829)

Utilizator leopop29Pop Leonard leopop29 Data 21 aprilie 2016 19:17:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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;
string s;
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;
    getline(f, s);
    for(int i = 1; i <= n; ++i)
    {
        getline(f, s);

        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 = q.front().x;
        cc = q.front().y;
        q.pop();

        if(mt[cp.x][cp.y])
            mt[cp.x][cp.y] = min(mt[cp.x][cp.y], cc);
        else
            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])
                q.push(mp(mp(a, b), cc+1));
        }
    }

    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));
        }
    }

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