Cod sursa(job #1279954)

Utilizator Andrei66Andrei Rusu Andrei66 Data 1 decembrie 2014 09:59:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define x first
#define y second

using namespace std;

vector <string> v;
int distr[105][105], distj[105][105];
int n, m;

bool is_inside(int x, int y){
    return (x>=0 && x<n && y>=0 && y<m);
}

void bfs(pair <int, int> romeo, int a[105][105]){
    queue <pair <int, int> > c;
    a[romeo.x][romeo.y] = 1;
    for(c.push(romeo); !c.empty(); c.pop()){
        pair <int, int> fr = c.front();
        for(int i=-1; i<=1;i++)
            for(int j=-1;j<=1;j++){
                int ii=fr.x+i,jj=fr.y+j;
                if(is_inside(ii,jj) && !a[ii][jj] && v[ii][jj] !='X'){
                        c.push(make_pair(ii,jj));
                        a[ii][jj]=a[fr.x][fr.y]+1;
                }
            }
    }
}

pair <int,int> find(char c){
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(v[i][j]==c)
                return make_pair(i,j);
    return make_pair(-1,-1);
}

int main() {
    ifstream f("rj.in");
    ofstream g("rj.out");
    //f.sync_with_stdio(false);
    f>>n>>m;
    f.get();
    for(int i=0;i<n;i++){
        string s;
        getline(f,s);
        v.push_back(s);
    }

    bfs(find('R'), distr);
    bfs(find('J'), distj);

    pair <int, int> j = find('J');
    pair <int, int> minp = j;
    int minn=distr[j.x][j.y];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(max(distr[i][j], distj[i][j])<minn && v[i][j]!='X' && distr[i][j] && distr[i][j]==distj[i][j]){
                minn=distr[i][j];
                minp=make_pair(i, j);
            }
    g<<minn<<" "<<minp.x+1<<" "<<minp.y+1;

    return 0;
}