Cod sursa(job #1187091)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 17 mai 2014 16:26:59
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<fstream>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int r[105][105],jl[105][105],v[105][105],n,m;
int d1[] = {-1,0,1,0,1,1,-1,-1};
int d2[] = {0,1,0,-1,1,-1,1,-1};

struct punct{
    int x;
    int y;
};
queue<struct punct> coada;

void solve(struct punct start,int m[][105])
{

    struct punct now;
    m[start.x][start.y] = 1;
    int i;
    coada.push(start);
    while(!coada.empty()){

        for(i = 0 ; i < 8 ; i++)
        {
            now.x = coada.front().x+d1[i];
            now.y = coada.front().y+d2[i];
            if(v[now.x][now.y] == 0 && !m[now.x][now.y]){
                m[now.x][now.y] = m[coada.front().x][coada.front().y] + 1;
                coada.push(now);
            }
         }
         coada.pop();
    }
}

int main()
{
    string s;
    int i,j;
    in>>n>>m;
    getline(in,s);
    struct punct romeo,julieta;
    for(i = 1 ; i <= n ; i++)
    {
        getline(in,s);
        for(j = 0 ; j <s.size() ; j++)
            {
                if(s[j] == 'R'){
                    romeo.x = i;
                    romeo.y = j+1;
                    v[i][j+1] = 1;
                }
                if(s[j] == 'J'){
                    julieta.x = i;
                    julieta.y = j+1;
                    v[i][j+1] = 1;
                 }
                 if(s[j] == 'X')
                    v[i][j+1] = 1;
                 if(s[j] == ' ')
                    v[i][j+1] = 0;
            }
    }
    for(i = 0 ; i <= n+1 ; i++)
        v[i][0] = v[i][m+1] = -1;
    for(j = 0 ; j <= m+1 ; j++)
        v[0][j] = v[n+1][j] = -1;
    solve(romeo,r);
    solve(julieta,jl);
    int sol = 999999999,c1,c2;
    for(i = 1 ; i <= n ; i++)
        for(j = 1 ; j <= m ; j++){
            if(r[i][j] != 0 && jl[i][j] !=0)
            if(r[i][j] == jl[i][j]){
                if(r[i][j] < sol){
                    sol = r[i][j];
                    c1 = i;
                    c2 = j;
                }
            }
    }
    out<<sol<<" "<<c1<<" "<<c2;
    return 0;
}