Cod sursa(job #1721559)

Utilizator antracodRadu Teodor antracod Data 25 iunie 2016 22:26:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

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

int a[101][101],n,m;

int dl[]= {-1,-1,-1,0,0,1,1,1};
int dc[]= {-1,0,1,-1,1,-1,0,1};
int rx,ry,jx,jy;

queue<int> Qx;
queue<int> Qy;

void citire()
{
    in>>n>>m;
    int i,j;
    char c[101];
    in.get();
    for(i=0; i<n; i++)
    {
        in.getline(c,105);
        for(j=0; j<m; j++)
        {

            if(c[j]=='R')
            {
                a[i][j]=1;
                Qx.push(i);
                Qy.push(j);
            }
            else if(c[j]=='J')
            {
                a[i][j]=-1;
                Qx.push(i);
                Qy.push(j);
            }
            else if(c[j]==' ')
            {
                a[i][j]=0;
            }
            else
            {
                a[i][j]=999999;
            }
        }
    }
}


int safe(int k,int n)
{
    if(Qx.front()+dl[k]<n && Qx.front()+dl[k]>=0 && Qy.front()+dc[k]<n && Qy.front()+dc[k]>=0)
        return 1;
    return 0;
}

void bfs()
{
    int k;
    while(Qx.empty()==0)
    {
        for(k=0; k<8; k++)
        {

            if(safe(k,n)==1)
            {
                if(a[Qx.front()+dl[k]][Qy.front()+dc[k]]<0 && a[Qx.front()][Qy.front()]>0 && a[Qx.front()][Qy.front()]!=999999)
                {
                    rx=Qx.front();
                    ry=Qy.front();
                    jx=Qx.front()+dl[k];
                    jy=Qy.front()+dc[k];
                }

                if(a[Qx.front()+dl[k]][Qy.front()+dc[k]]==0)
                {
                    Qx.push(Qx.front()+dl[k]);
                    Qy.push(Qy.front()+dc[k]);
                    if(a[Qx.front()][Qy.front()]>0)
                        a[Qx.front()+dl[k]][Qy.front()+dc[k]]=a[Qx.front()][Qy.front()]+1;
                    else
                        a[Qx.front()+dl[k]][Qy.front()+dc[k]]=a[Qx.front()][Qy.front()]-1;
                }
            }
        }
        Qx.pop();
        Qy.pop();
    }

}

int main()
{
    int i,j;
    citire();
    bfs();
    a[jx][jy]=-a[jx][jy];

    if(a[rx][ry]>a[jx][jy])
    {
        out<<a[jx][jy]+1;
    }
    else
        out<<a[rx][ry];


    out<<" ";
    if(rx<jx)
    {
        out<<rx+1<<" "<<ry+1;
    }
    else if(rx==jx)
    {
        if(ry<jy)
            out<<rx+1<<" "<<ry+1;
        else
            out<<jx+1<<" "<<jy+1;
    }
    else
    {
        out<<jx+1<<" "<<jy+1;
    }

}