Cod sursa(job #699717)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 29 februarie 2012 20:56:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <string.h>
#include <queue>

using namespace std;

int mat[110][110],drumro[110][110],drumju[110][110],i,n,m;

queue<int>Qi;
queue<int>Qj;

int di[8]={-1,0,1,1,1,0,-1,-1};
int dj[8]={-1,-1,-1,0,1,1,1,0};

void lee1()
{
    int a,b;
    while (!Qi.empty())
    {
        a=Qi.front();
        b=Qj.front();
        Qi.pop();
        Qj.pop();
        for (i=0;i<8;i++)
        {
            if (a+di[i]>0&&a+di[i]<=n&&b+dj[i]>0&&b+dj[i]<=m)
            {
                if (drumro[a+di[i]][b+dj[i]]==0&&mat[a+di[i]][b+dj[i]]!=-1)
                {
                    drumro[a+di[i]][b+dj[i]]=drumro[a][b]+1;
                    Qi.push(a+di[i]);
                    Qj.push(b+dj[i]);
                }
            }
        }
    }
}

void lee2()
{
    int a,b;
    while (!Qi.empty())
    {
        a=Qi.front();
        b=Qj.front();
        Qi.pop();
        Qj.pop();
        for (i=0;i<8;i++)
        {
            if (a+di[i]>0&&a+di[i]<=n&&b+dj[i]>0&&b+dj[i]<=m)
            {
                if (drumju[a+di[i]][b+dj[i]]==0&&mat[a+di[i]][b+dj[i]]!=-1)
                {
                    drumju[a+di[i]][b+dj[i]]=drumju[a][b]+1;
                    Qi.push(a+di[i]);
                    Qj.push(b+dj[i]);
                }
            }
        }
    }
}

int main()
{
    ifstream in ("rj.in");
    ofstream out ("rj.out");
    int j,x1,x2,y1,y2;
    in>>n>>m;
    char s[120];
    in.get();
    for (i=1;i<=n;i++)
    {
        in.getline(s,120);
        for (j=0;j<m;j++)
        {
            if (s[j]=='X')
                mat[i][j+1]=-1;
            if (s[j]=='R')
            {
                x1=i;
                y1=j+1;
                mat[i][j+1]=1;
            }
            if (s[j]=='J')
            {
                x2=i;
                y2=j+1;
                mat[i][j+1]=1;
            }
        }
    }
    Qi.push(x1);
    Qj.push(y1);
    drumro[x1][y1]=1;
    lee1();
    Qi.push(x2);
    Qj.push(y2);
    drumju[x2][y2]=1;
    lee2();
    int x,y,tmax=1000;

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (drumro[i][j]==drumju[i][j]&&drumro[i][j]!=0)
            {
                if (tmax>drumro[i][j])
                {
                    x=i;
                    y=j;
                    tmax=drumro[i][j];
                }
            }
        }
    }
    out<<tmax<<" "<<x<<" "<<y<<"\n";
    /*for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            out<<drumro[i][j]<<" ";
        out<<"\n";
    }
    for (i=1;i<=n;i++)
    {
        out<<"\n";
        for (j=1;j<=m;j++)
            out<<drumju[i][j]<<" ";
    }
    out<<"\n";
    for (i=1;i<=n;i++)
    {
        out<<"\n";
        for (j=1;j<=m;j++)
            out<<mat[i][j]<<" ";
    }*/
    return 0;
}