Cod sursa(job #2204000)

Utilizator asavoaeigeoAsavoaei Georgiana asavoaeigeo Data 14 mai 2018 00:24:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <queue>
#include <cstring>
#define nmax 101
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n, m;
int matR[nmax][nmax], matJ[nmax][nmax];
int dy[8]={0,1,1,1,0,-1,-1,-1};
int dx[8]={-1,-1,0,1,1,1,0,-1};

struct punct
{
    int x, y;
};
punct R, J;
void Citire()
{
    int i, j;
    char c;
    char s[nmax];
    fin>>n>>m;
    fin.get();
    for(i=1; i<=n; i++)
    {
        fin.getline(s,m+1);
        for(j=1; j<=m; j++)
        {
            if(s[j-1]==' ')matR[i][j]=matJ[i][j]=0;
            else if(s[j-1]=='X') matR[i][j]=matJ[i][j]=-1;
            if(s[j-1]=='R')
            {
                R.x=i;
                R.y=j;
            }
            if(s[j-1]=='J')
            {
                J.x=i;
                J.y=j;
            }
        }
    }
}

void Bordare(int matrice[nmax][nmax])
{
    for(int j=0; j<=m+1; j++)
        matrice[0][j]=matrice[n+1][j]=-1;
    for(int i=0; i<=n+1; i++)
        matrice[i][0]=matrice[i][m+1]=-1;
}

int Drum(punct start, punct sfarsit, int matrice[nmax][nmax])
{
    queue<int> Q1, Q2;
    Q1.push(start.x);
    Q2.push(start.y);
    matrice[start.x][start.y]=1;
    while(!Q1.empty())
    {
        int l=Q1.front();
        int c=Q2.front();
        Q1.pop();
        Q2.pop();
        for(int i=0; i<8; i++)
        {
            int a=l+dx[i];
            int b=c+dy[i];
            if(matrice[a][b]==0  )
            {
                matrice[a][b]=matrice[l][c]+1;
                Q1.push(a);
                Q2.push(b);
            }
            if(a==sfarsit.x && b==sfarsit.y) return matrice[a][b];
        }
    }

}
int main()
{
    Citire();
    Bordare(matR);
    Bordare(matJ);
    int x=Drum(R, J, matR);
    int y=Drum(J, R, matJ);
    int dmin=nmax*nmax;
    punct Solutie;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(matR[i][j] &&matJ[i][j]>1)
                if(matR[i][j]==matJ[i][j])
                    if(matR[i][j]<dmin)
                    {
                        dmin=matR[i][j];
                        Solutie.x=i;
                        Solutie.y=j;
                    }
    fout<<dmin<<" "<<Solutie.x<<" "<<Solutie.y;

    return 0;
}