Cod sursa(job #1593149)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 8 februarie 2016 12:47:44
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
char a[101][105];
int b[101][101],c[101][101],n,m;
pair<int,int>Romeo,Julieta;
int di[]={ 0, 1, 0,-1, 1,-1, 1,-1};
int dj[]={ 1, 0,-1, 0, 1,-1,-1, 1};
struct{int i,j;}x;
int tmin=9999999;
int ok(int i,int j)
{
    if(i<1 || i>n || j<1 || j>m)
        return 0;
    if(a[i][j]=='X')
        return 0;
    return 1;
}
void lee1()
{
    queue<pair<int,int> >q;
    q.push(make_pair(Romeo.first,Romeo.second));
    int i,j,ni,nj;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(int d=0;d<8;d++)
        {
            ni=i+di[d];
            nj=j+dj[d];
            if(ok(ni,nj) && b[ni][nj]<1)
            {
                b[ni][nj]=b[i][j]+1;
                q.push(make_pair(ni,nj));
            }
        }
    }
}
void lee2()
{
    queue<pair<int,int> >q;
    q.push(make_pair(Julieta.first,Julieta.second));
    int i,j,ni,nj;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        if(c[i][j]==b[i][j] && c[i][j]<=tmin)
        {
            tmin=c[i][j];
            x.i=i;
            x.j=j;
        }
        q.pop();
        for(int d=0;d<8;d++)
        {
            ni=i+di[d];
            nj=j+dj[d];
            if(ok(ni,nj) && c[ni][nj]<1)
            {
                c[ni][nj]=c[i][j]+1;
                q.push(make_pair(ni,nj));
            }
        }
    }
}
int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
        fin.getline(a[i]+1,100,'\n');
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='R')
            {
                Romeo.first=i;
                Romeo.second=j;
            }
            else if(a[i][j]=='J')
            {
                Julieta.first=i;
                Julieta.second=j;
            }
        }
    }
    lee1();
    lee2();
    fout<<tmin+1<<' '<<x.i<<' '<<x.j;
    fout.close();
    return 0;
}