Cod sursa(job #791880)

Utilizator harababurelPuscas Sergiu harababurel Data 25 septembrie 2012 17:58:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define nmax 105
#define inf 99999999
#define x first
#define y second
using namespace std;


char a[nmax][nmax];
int cost[2][nmax][nmax];
int n, m;
vector < pair <int, int> > ind;
pair <int, int> nod, protagonist[2];
queue < pair <int, int> > q;

int nu_iese_cumva_din_matrice(int newx, int newy) {
    if(newx >= 1 && newx <= n && newy >= 1 && newy <= m) return 1;
    return 0;
}

void bfs(int p) {
    cost[p][protagonist[p].x][protagonist[p].y] = 0;
    q.push(make_pair(protagonist[p].x, protagonist[p].y));

    while(!q.empty()) {
        nod.x = q.front().x;
        nod.y = q.front().y;
        q.pop();

        for(int i = 0; i < ind.size(); i++) {
            int newx = nod.x + ind[i].x;
            int newy = nod.y + ind[i].y;
            if(nu_iese_cumva_din_matrice(newx, newy))
                if(a[newx][newy] != 'X' && cost[p][newx][newy] == -1) {
                    cost[p][newx][newy] = cost[p][nod.x][nod.y] + 1;
                    q.push(make_pair(newx, newy));
                }
        }
    }

}

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

    int i, j;

    f>>n>>m;                        //citire
    f.get();
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            a[i][j] = f.get();
            if(a[i][j]=='R') protagonist[0].x = i, protagonist[0].y = j;
            if(a[i][j]=='J') protagonist[1].x = i, protagonist[1].y = j;
        }
        f.get();
    }

    for(i=-1; i<=1; i++)
        for(j=-1; j<=1; j++)
            ind.push_back(make_pair(i, j));

    for(i=0; i<=n+1; i++)
        for(j=0; j<=m+1; j++)
            cost[0][i][j] = -1, cost[1][i][j] = -1;

    bfs(0);     //pentru ROMEO
    bfs(1);     //si pentru JULIETA

    int solx=0, soly=0, minim = inf, timp;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(cost[0][i][j]!=-1 && cost[1][i][j]!=-1) {
                timp = max(cost[0][i][j], cost[1][i][j]) + 1;
                if(timp < minim && abs(cost[1][i][j]-cost[0][i][j]) == 0) {
                    minim = timp;
                    solx = i;
                    soly = j;
                }
            }

    g<<minim<<" "<<solx<<" "<<soly<<"\n";

    f.close();
    g.close();
    return 0;
}