Cod sursa(job #2174525)

Utilizator cristiancristea_2010Cristian Cristea cristiancristea_2010 Data 16 martie 2018 12:26:23
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int N,M,r[102][102],ju[102][102],ri,rj,ji,jj,i,j,q[500],p=0,minim=203,fi,fj;
char s[102][102];
const int dx[8]={-1,0,1,0,-1,-1,1,1};
const int dy[8]={0,1,0,-1,-1,1,1,-1};

int verificar(int i,int j)
{
    if ((i<1||i>N||j<1||j>M)||(r[i][j]!=0)) return 0;
        else return 1;
}
int verificaj(int x,int y)
{
    if ((x<1 || x>N || y<1 || y>M) || (ju[x][y]!=0)) return 0;
    else return 1;
}
void adauga(int x)
{
    q[p]=x;
    p++;
}

void sterge()
{
    for (int i=0;i<p-1;i++)
        q[i]=q[i+1];
    p--;
}

int vida()
{
    if (p==0) return 1;
    else return 0;
}

int primul()
{
    return q[0];
}

void leer()
{
    adauga(ri);
    adauga(rj);
    r[ri][rj]=1;
    while (vida()==0)
    {
        i=primul();
        sterge();
        j=primul();
        sterge();
        for (int k=0;k<8;k++)
        {
            if (verificar(i+dx[k],j+dy[k])==1)
            {
                r[i+dx[k]][j+dy[k]]=r[i][j]+1;
                adauga(i+dx[k]);
                adauga(j+dy[k]);
            }
        }
    }
}

void leej()
{
    adauga(ji);
    adauga(jj);
    ju[ji][jj]=1;
    while (vida()==0)
    {
        i=primul();
        sterge();
        j=primul();
        sterge();
        for (int k=0;k<8;k++)
        {
            if (verificaj(i+dx[k],j+dy[k])==1)
            {
                adauga(i+dx[k]);
                adauga(j+dy[k]);
                ju[i+dx[k]][j+dy[k]]=ju[i][j]+1;
            }
        }
    }
}
int main()
{
    f>>N>>M;
    f.get();
    for (int i=1;i<=N;i++)
    {
        f.getline(s[i],102);
        for (int j=M;j>=1;j--)
        {
            s[i][j]=s[i][j-1];
        }
    }
    for (int i=1;i<=N;i++)
        for (int j=1;j<=M;j++)
        {
            if (s[i][j]=='X')
            {
                r[i][j]=-1;
                ju[i][j]=-1;
            }
            else
            {
                r[i][j]=0;
                ju[i][j]=0;
            }
            if (s[i][j]=='R')
            {
                ri=i;
                rj=j;
            }
            if (s[i][j]=='J')
            {
                ji=i;
                jj=j;
            }
        }
    leer();
    leej();
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            if (r[i][j]==ju[i][j] && r[i][j]<minim && r[i][j]!=-1 && r[i][j]!=0 && ju[i][j]!=0)
            {
                fi=i;
                fj=j;
                minim=r[i][j];
            }
        }
    }
    g<<minim<<" "<<fi<<" "<<fj;

}