Cod sursa(job #1436119)

Utilizator dumbraveanbDumbravean Bogdan dumbraveanb Data 15 mai 2015 09:32:45
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;

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

int A[101][101],B[101][101],a[10001],b[10001],n,m,is,js,ib,jb,dmin = 10000, imin, jmin;
const int di[]={-1,0,1,0,1,1,-1,-1}, dj[]={0,1,0,-1,1,-1,1,-1};
char c[102];

int inside(int i,int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        fin.getline(c,102);
        for(int j=0;j<strlen(c);j++)
        {
            if(c[j]==' ') {A[i][j+1]=0; B[i][j+1]=0;}
            else if(c[j]=='X') {A[i][j+1]=-1; B[i][j+1]=-1;}
            else if(c[j]=='R') {A[i][j+1]=1; is=i; js=j + 1; B[i][j+1]=1;}
            else if(c[j]=='J') {A[i][j+1]=1; ib=i; jb=j + 1; B[i][j+1]=1;}
        }
    }

    a[1]=is; b[1]=js; A[is][js]=1;
    int s=1,d=1;
    while (s<=d && !(a[s]==ib && b[s]==jb))
    {
        int i=a[s],j=b[s];
        for(int k=0;k<8;k++)
        {
            int inou=i+di[k], jnou=j+dj[k];
            if(inside(inou,jnou) && A[inou][jnou]==0)
            {
                A[inou][jnou]=A[i][j]+1;
                d++;
                a[d]=inou; b[d]=jnou;
            }
        }
        s++;
    }
    int aux1,aux2;
    a[1]=ib; b[1]=jb; B[ib][jb]=1;
    s=1,d=1;
    while (s<=d && !(a[s]==is && b[s]==js))
    {
        int i=a[s],j=b[s];
        for(int k=0;k<8;k++)
        {
            int inou=i+di[k], jnou=j+dj[k];
            if(inside(inou,jnou) && B[inou][jnou]==0)
            {
                B[inou][jnou]=B[i][j]+1;
                d++;
                a[d]=inou; b[d]=jnou;
            }
        }
        s++;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(A[i][j] > 1 && B[i][j] > 1)
            {
                if(A[i][j] >= B[i][j] && A[i][j] < dmin) {dmin = A[i][j]; imin = i; jmin = j;}
                else if(A[i][j] < B[i][j] && B[i][j] < dmin) {dmin = B[i][j]; imin = i; jmin = j;}
            }
    fout << dmin << ' ' << imin << ' ' << jmin;
    return 0;
}