Cod sursa(job #1451380)

Utilizator ciocan_catalinCiocan Catalin - Iulian ciocan_catalin Data 16 iunie 2015 21:40:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m,a[105][105],r[105][105],jul[105][105];
int dx[] = {0,1,0,-1,1,-1,-1,1};
int dy[] = {1,0,-1,0,1,1,-1,-1};
int xr,yr,xj,yj;
queue < pair <int, int> > Q;
void Read()
{
    int i,j;
    char c[210];
    fin>>n>>m;
     fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(c,200);
        for(j=0;j<m;j++)
    {
        if(c[j]==' ') a[i][j+1] = 0;
        else if(c[j]=='X') a[i][j+1] = 1;
        else if(c[j]=='R')
        {
            xr = i;
            yr = j+1;
        }
        else if(c[j]=='J')
        {
            xj = i;
            yj = j+1;
        }
    }
    }
}

bool OK(int i, int j)
{
    if(i<1 || i>n || j<1 || j>n || a[i][j]==1)
        return false;
    return true;
}

void LeeRomeo()
{
    int i,j,i_next,j_next,dir;
    r[xr][yr] = 1;
    Q.push(make_pair(xr,yr));
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(dir = 0; dir < 8; dir++)
        {
            i_next = i + dx[dir];
            j_next = j + dy[dir];
            if(OK(i_next,j_next) && r[i_next][j_next]==0)
            {
                r[i_next][j_next] = 1+r[i][j];
                Q.push(make_pair(i_next,j_next));
            }
        }
    }

}

void LeeJulieta()
{
    int i,j,i_next,j_next,dir;
    jul[xj][yj] = 1;
    Q.push(make_pair(xj,yj));
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(dir = 0; dir < 8; dir++)
        {
            i_next = i + dx[dir];
            j_next = j + dy[dir];
            if(OK(i_next,j_next) && jul[i_next][j_next]==0)
            {
                jul[i_next][j_next] = 1+jul[i][j];
                Q.push(make_pair(i_next,j_next));
            }
        }
    }
}

void Solve()
{
    int i,j,tmin,x,y;
    tmin = 100000000;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(r[i][j]==jul[i][j] && r[i][j]!=0 && tmin>r[i][j])
            {

              tmin = r[i][j];
              x = i;
              y = j;
            }
    fout<<tmin<<" "<<x<<" "<<y<<"\n";
}


int main()
{
    Read();
    LeeRomeo();
    LeeJulieta();
    Solve();
    fout.close();
    return 0;
}