Cod sursa(job #1611467)

Utilizator remus88Neatu Remus Mihai remus88 Data 24 februarie 2016 09:52:39
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
#include <queue>
#include <bitset>
#define Nmax 109

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

struct point
{
    int x,y;
    point(){
    }
    point(int i, int j)
    {
        x=i;
        y=j;
    }
};

int n,m,j[Nmax][Nmax],r[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};
char c[10][10];
point rom,jul;
queue <point> Q;
bitset <Nmax> inQ[Nmax];

void RomLee(int sx, int sy)
{
    r[sx][sy]=a[sx][sy];
    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 && (r[p][q]==0 || r[p][q]>r[x][y]+1))
                {
                    r[p][q]=r[x][y]+1;
                    if (!inQ[p][q])
                    {
                        Q.push(point(p,q));
                        inQ[p][q]=1;
                    }
                }
            }
        }
}

void JulLee(int sx, int sy)
{
    j[sx][sy]=a[sx][sy];
    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 && (j[p][q]==0 || j[p][q]>j[x][y]+1))
                {
                    j[p][q]=j[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; ++i)
        for (int j=1; j<=m; ++j)
        {


            //if (c==' ') a[i][j]=0;
            /*if (c=='X') a[i][j]=1;
            if (c=='R')
            {
                a[i][j]=0;
                rom.x=i;
                rom.y=j;
            }
            if (c=='J')
            {
                a[i][j]=0;
                jul.x=i;
                jul.y=j;
            }*/
        }
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<c[i][j];
        g<<'\n';
    }
    RomLee(rom.x,rom.y);
    while (!Q.empty())
    {
        Q.pop();
    }
    inQ[Nmax].reset();
    JulLee(jul.x,jul.y);
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<r[i][j]<<' ';
        g<<'\n';
    }
    for (int i=1; i<=n; ++i)
    {
        for (int k=1; k<=m; ++k) g<<j[i][k]<<' ';
        g<<'\n';
    }
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j) g<<a[i][j]<<' ';
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}