Cod sursa(job #1396418)

Utilizator bluespideyMarin Diana bluespidey Data 22 martie 2015 15:08:08
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define x first
#define y second
#define punct pair<int,int>

using namespace std;

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

int n,i,l,k,a,m[101][101],b,j,M,nr,m1[101][101],m2[101][101],mini=1000;
queue <punct> Q;
char c;
bool ok;
string st;
punct now,now2,finish,nowr,nowj;
int DX[] = {-1,0,1,0,1,-1,1,-1};
int DY[] = {0,-1,0,1,-1,1,1,-1};

bool verif1(punct s)
{
    if((s.x>0)&&(s.y>0)&&(s.x<=n)&&(s.y<=M)&&(!m[s.x][s.y])&&(!m1[s.x][s.y]))
        return 1;
    else return 0;
}
bool verif2(punct ss)
{
    if((ss.x>0)&&(ss.y>0)&&(ss.x<=n)&&(ss.y<=M)&&(!m[ss.x][ss.y])&&(!m2[ss.x][ss.y]))
        return 1;
    else return 0;
}

int main()
{
    fin >> n >> M;
    getline(fin,st);

    for(i = 1; i <= n; ++i)
            {
                getline(fin,st);
                for(j = 0; j < M; ++j)
                if(st[j]=='R')
                    nowr = make_pair(i,j+1);
                else if(st[j]=='J')
                    nowj = make_pair(i,j+1);
                    else if(st[j]=='X')
                        m[i][j+1] = -1;
            }


    Q.push(nowr);
    m1[nowr.x][nowr.y]=m2[nowj.x][nowj.y] = 1;

    while(Q.size())
    {
        now = Q.front();
        Q.pop();

        for(k = 0; k < 8; ++k)
            {
                now2.x = now.x + DX[k];
                now2.y = now.y + DY[k];

                if(verif1(now2))
                    {
                        Q.push(now2);
                        m1[now2.x][now2.y] = m1[now.x][now.y]+1;
                    }
            }
    }
    Q.push(nowj);
    while(Q.size())
    {
        now = Q.front();
        Q.pop();

        for(k = 0; k < 8; ++k)
            {
                now2.x = now.x + DX[k];
                now2.y = now.y + DY[k];

                if(verif2(now2))
                    {
                        Q.push(now2);
                        m2[now2.x][now2.y] = m2[now.x][now.y]+1;
                    }
            }
    }

    for(i = 1; i <= n; ++i)
        for(j = 1; j <= M; ++j)
            if((m1[i][j]==m2[i][j])&&(m1[i][j]))
                if(m1[i][j]<mini)
                    {
                        mini = m1[i][j];
                        a = i;
                        b = j;
                    }

    fout << mini <<" "<<a << " "<< b;


    return 0;
}