Cod sursa(job #1373085)

Utilizator MaRryUuSManea Marius MaRryUuS Data 4 martie 2015 16:44:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue <int> qx;
queue <int> qy;
char h[102][102];
struct harta
{
    int r,j;
}a[102][102];
void R_lee(int x,int y)
{
    qx.push(x);
    qy.push(y);
    while(qx.empty()!=true)
    {
        x=qx.front();
        y=qy.front();
        if(a[x-1][y].r==-1||a[x-1][y].r>a[x][y].r+1){a[x-1][y].r=a[x][y].r+1; qx.push(x-1); qy.push(y);} //sus
        if(a[x-1][y+1].r==-1||a[x-1][y+1].r>a[x][y].r+1){a[x-1][y+1].r=a[x][y].r+1; qx.push(x-1); qy.push(y+1);} //dreapta sus
        if(a[x][y+1].r==-1||a[x][y+1].r>a[x][y].r+1){a[x][y+1].r=a[x][y].r+1; qx.push(x); qy.push(y+1);} //dreapta
        if(a[x+1][y+1].r==-1||a[x+1][y+1].r>a[x][y].r+1){a[x+1][y+1].r=a[x][y].r+1; qx.push(x+1); qy.push(y+1);} //dreapta jos
        if(a[x+1][y].r==-1||a[x+1][y].r>a[x][y].r+1){a[x+1][y].r=a[x][y].r+1; qx.push(x+1); qy.push(y);} //jos
        if(a[x+1][y-1].r==-1||a[x+1][y-1].r>a[x][y].r+1){a[x+1][y-1].r=a[x][y].r+1; qx.push(x+1); qy.push(y-1);} //stanga jos
        if(a[x][y-1].r==-1||a[x][y-1].r>a[x][y].r+1){a[x][y-1].r=a[x][y].r+1; qx.push(x); qy.push(y-1);} //stanga
        if(a[x-1][y-1].r==-1||a[x-1][y-1].r>a[x][y].r+1){a[x-1][y-1].r=a[x][y].r+1; qx.push(x-1); qy.push(y-1);} //stanga sus
        qx.pop(); qy.pop();
    }
}
void J_lee(int x,int y)
{
    qx.push(x);
    qy.push(y);
    while(qx.empty()!=true)
    {
        x=qx.front();
        y=qy.front();
        if(a[x-1][y].j==-1||a[x-1][y].j>a[x][y].j+1){a[x-1][y].j=a[x][y].j+1; qx.push(x-1); qy.push(y);} //sus
        if(a[x-1][y+1].j==-1||a[x-1][y+1].j>a[x][y].j+1){a[x-1][y+1].j=a[x][y].j+1; qx.push(x-1); qy.push(y+1);} //dreapta sus
        if(a[x][y+1].j==-1||a[x][y+1].j>a[x][y].j+1){a[x][y+1].j=a[x][y].j+1; qx.push(x); qy.push(y+1);} //dreapta
        if(a[x+1][y+1].j==-1||a[x+1][y+1].j>a[x][y].j+1){a[x+1][y+1].j=a[x][y].j+1; qx.push(x+1); qy.push(y+1);} //dreapta jos
        if(a[x+1][y].j==-1||a[x+1][y].j>a[x][y].j+1){a[x+1][y].j=a[x][y].j+1; qx.push(x+1); qy.push(y);} //jos
        if(a[x+1][y-1].j==-1||a[x+1][y-1].j>a[x][y].j+1){a[x+1][y-1].j=a[x][y].j+1; qx.push(x+1); qy.push(y-1);} //stanga jos
        if(a[x][y-1].j==-1||a[x][y-1].j>a[x][y].j+1){a[x][y-1].j=a[x][y].j+1; qx.push(x); qy.push(y-1);} //stanga
        if(a[x-1][y-1].j==-1||a[x-1][y-1].j>a[x][y].j+1){a[x-1][y-1].j=a[x][y].j+1; qx.push(x-1); qy.push(y-1);} //stanga sus
        qx.pop(); qy.pop();
    }
}
void citire(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        f.get();
        f.get(h[i],102);
    }
}
void transformare(int n,int m,int &xr,int &yr, int &xj, int &yj)
{
    int i,k;
    char c;
    for(i=1;i<=n;i++)
        for(k=0;k<m;k++)
            {
                c=h[i][k];
                if(c==' '){a[i][k+1].r=-1; a[i][k+1].j=-1;}
                    else if(c=='X'){a[i][k+1].r=-2; a[i][k+1].j=-2;}
                            else if(c=='R'){a[i][k+1].r=0; a[i][k+1].r=1; xr=i; yr=k+1;}
                                    else if(c=='J'){a[i][k+1].j=0; a[i][k+1].j=1; xj=i; yj=k+1;}
            }
}
void solutie(int &tmin,int &solx,int &soly,int n,int m)
{
    int i,k;
    for(i=1;i<=n;i++)
        for(k=1;k<=m;k++)
            if(a[i][k].r<tmin&&a[i][k].r==a[i][k].j&&a[i][k].r>0){tmin=a[i][k].r; solx=i; soly=k;}
}
int main()
{
    int n,m,tmin=32000,solx,soly,xr,yr,xj,yj;
    f>>n>>m;
    citire(n); // construim harta
    transformare(n,m,xr,yr,xj,yj); // impartim harta celor doi
    R_lee(xr,yr); // harta lui Romeo
    J_lee(xj,yj); // harta Julietei
    solutie(tmin,solx,soly,n,m); // punctul de intalnire
    g<<tmin<<" "<<solx<<" "<<soly;
    return 0;
}