Cod sursa(job #1611693)

Utilizator remus88Neatu Remus Mihai remus88 Data 24 februarie 2016 12:47:32
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <queue>
#include <bitset>
#include <cstring>
#define Nmax 109

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
#define x first
#define y second

typedef pair <int,int> point;

int n,m,jul[Nmax][Nmax],rom[Nmax][Nmax],a[Nmax][Nmax],nr,cnt;
int dx[10]={8,-1,-1,0,1,1,1,0,-1};
int dy[10]={8,0,1,1,1,0,-1,-1,-1};
string c;
point romeo,julieta,sol;
queue <point> Q;
bitset <Nmax> inQ[Nmax];

void RomLee(int sx, int sy)
{
    rom[sx][sy]=1;
    Q.push(point(sx,sy));
    inQ[sx][sy]=1;
    while (!Q.empty())
    {
        point curent=Q.front();
        Q.pop();
        int x=curent.x;
        int y=curent.y;
        inQ[x][y]=0;

        for (int k=1; k<=8; ++k)
            {
                int p=x+dx[k];
                int q=y+dy[k];
                if (p>=1 && p<=n && q>=1 && q<=m && a[p][q]==0 && (rom[p][q]==0 || rom[p][q]>rom[x][y]+1))
                {
                    rom[p][q]=rom[x][y]+1;
                    if (!inQ[p][q])
                    {
                        Q.push(point(p,q));
                        inQ[p][q]=1;
                    }
                }
            }
        }
}

void JulLee(int sx, int sy)
{

    jul[sx][sy]=1;
    Q.push(point(sx,sy));
    inQ[sx][sy]=1;
    while (!Q.empty())
    {
        point curent=Q.front();
        Q.pop();
        int x=curent.x;
        int y=curent.y;
        inQ[x][y]=0;

        for (int k=1; k<=8; ++k)
            {
                int p=x+dx[k];
                int q=y+dy[k];
                if (p>=1 && p<=n && q>=1 && q<=m && a[p][q]==0 && (jul[p][q]==0 || jul[p][q]>jul[x][y]+1))
                {
                    jul[p][q]=jul[x][y]+1;
                    if (!inQ[p][q])
                    {
                        Q.push(point(p,q));
                        inQ[p][q]=1;
                    }
                }
            }
        }
}

int main()
{
    f>>n>>m;
    for (int i=1; i<=n+1; ++i)
    {
        getline(f,c);
       // g<<c<<'\n';
        for (int j=1; j<=m; ++j)
        {
            if (c[j-1]=='R') romeo=point(i-1,j);
            if (c[j-1]=='J') julieta=point(i-1,j);
            if (c[j-1]=='X') a[i-1][j]=1;
        }
    }
    RomLee(romeo.x,romeo.y);
    JulLee(julieta.x,julieta.y);
   /* for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<a[i][j];
        g<<'\n';
    }
    g<<'\n';
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<rom[i][j]<<' ';
        g<<'\n';
    }
    g<<'\n';
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<jul[i][j]<<' ';
        g<<'\n';
    }
    g<<'\n';
    g<<romeo.x<<' '<<romeo.y<<'\n';
    g<<julieta.x<<' '<<julieta.y<<'\n';*/
    int minn=100000;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
            if (rom[i][j]==jul[i][j] && rom[i][j]<minn && rom[i][j]!=0)
            {
                minn=rom[i][j];
                sol=point(i,j);
            }
    g<<minn<<' '<<sol.x<<' '<<sol.y<<'\n';
    f.close();
    g.close();
    return 0;
}