Cod sursa(job #791877)

Utilizator harababurelPuscas Sergiu harababurel Data 25 septembrie 2012 17:46:58
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 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 costr[nmax][nmax], costj[nmax][nmax];
int n, m;
vector < pair <int, int> > ind;
pair <int, int> rm, jl, nod;
queue < pair <int, int> > q;

void bfsr() {
    costr[rm.x][rm.y] = 0;
    q.push(make_pair(rm.x, rm.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(newx >= 1 && newx <= n && newy >= 1 && newy <= m)
                if(a[newx][newy] != 'X' && costr[newx][newy] == -1) {
                    costr[newx][newy] = costr[nod.x][nod.y] + 1;
                    q.push(make_pair(newx, newy));
                }
        }
    }

}
void bfsj() {
    costj[jl.x][jl.y] = 0;
    while(!q.empty()) q.pop();
    q.push(make_pair(jl.x, jl.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(newx >= 1 && newx <= n && newy >= 1 && newy <= m)
                if(a[newx][newy] != 'X' && costj[newx][newy] == -1) {
                    costj[newx][newy] = costj[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++) {
        //cout<<"<";
        for(j=1; j<=m; j++) {
            a[i][j] = f.get();
            if(a[i][j]=='R') rm.x = i, rm.y = j;
            if(a[i][j]=='J') jl.x = i, jl.y = j;
            //cout<<a[i][j];
        }
        f.get();
        //cout<<">\n";
    }

    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++)
            costj[i][j] = -1, costr[i][j] = -1;
    //cout<<rm.x<<" "<<rm.y<<"\n";
    //cout<<jl.x<<" "<<jl.y<<"\n";
    bfsr();
    bfsj();

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

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

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