Cod sursa(job #78218)

Utilizator cos_minBondane Cosmin cos_min Data 15 august 2007 22:49:23
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "rj.in"
#define out "rj.out"
#define dim 101
#define infinit 10000001

int N, M;
bool X[101][101];
int A[101][101], B[101][101];
int C1[2][101], C2[2][101];
int ipR, jpR, ipJ, jpJ;

const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dj[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

int OkR(int,int);
void SolveR();
int OkJ(int,int);
void SolveJ();

int main()
{
    char linie[103];
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fscanf(fin,"%d%d\n", &N, &M);
    for ( int i = 1; i <= N; i++ )
    {
        fgets(linie,M+2,fin);
        int j = 0;
        while ( j <= M )
        {
              if ( linie[j] == 'R' ) ipR = i, jpR = j+1, X[i][j+1] = 1;
              else if ( linie[j] == 'J' ) ipJ = i, jpJ = j+1, X[i][j+1] = 1;
              else if ( linie[j] == ' ' ) X[i][j+1] = 1;
              else if ( linie[j] == 'X' ) X[i][j+1] = 0;
              j++;
        }    
    }
    
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
            A[i][j] = B[i][j] = infinit;
    
    SolveR();
    SolveJ();
    
   /* for ( int i = 1; i <= N; i++, printf("\n") )
        for ( int j = 1; j <= M; j++ )
        {
            printf("%d ", B[i][j]);
        }*/
    
    int minim = infinit;
    int Rx, Ry;
    
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
        {
            if ( A[i][j] == B[i][j] && A[i][j] != infinit && minim > A[i][j] ) Rx = i, Ry = j, minim = A[i][j];
        }
    
    printf("%d %d %d", minim, Rx, Ry);
  
}

void SolveR()
{
     int p, u, i, j, ivec, jvec;
     
     p = u = 1; 
     C1[0][p] = ipR;
     C1[1][p] = jpR;
     A[ipR][jpR] = 1;
     
     while ( p )
     {
           u = 0;
           for ( int s = 1; s <= p; s++ )
           {
               i = C1[0][s];
               j = C1[1][s];
               for ( int dir = 0; dir < 8; dir++ )
               {
                   ivec = i+di[dir];
                   jvec = j+dj[dir];
                   
                   if ( OkR(ivec,jvec) && A[ivec][jvec] > A[i][j] + 1 )
                   {
                        A[ivec][jvec] = A[i][j] + 1;
                        u++;
                        C2[0][u] = ivec;
                        C2[1][u] = jvec;
                   }
               }
           }
           p = u;
           for ( int s = 1; s <= p; s++ )
               C1[0][s] = C2[0][s], C1[1][s] = C2[1][s];
     }
}

int OkR(int i, int j)
{
    if ( i < 1 || i > N || j < 1 || j > M ) return 0;
    if ( X[i][j] == 0 ) return 0;
    return 1;
}

void SolveJ()
{
     int p, u, i, j, ivec, jvec;
     
     p = u = 1; 
     C1[0][p] = ipJ;
     C1[1][p] = jpJ;
     B[ipJ][jpJ] = 1;
     
     while ( p )
     {
           u = 0;
           for ( int s = 1; s <= p; s++ )
           {
               i = C1[0][s];
               j = C1[1][s];
               for ( int dir = 0; dir < 8; dir++ )
               {
                   ivec = i+di[dir];
                   jvec = j+dj[dir];
                   
                   if ( OkJ(ivec,jvec) && B[ivec][jvec] > B[i][j] + 1 )
                   {
                        B[ivec][jvec] = B[i][j] + 1;
                        u++;
                        C2[0][u] = ivec;
                        C2[1][u] = jvec;
                   }
               }
           }
           p = u;
           for ( int s = 1; s <= p; s++ )
               C1[0][s] = C2[0][s], C1[1][s] = C2[1][s];
     }
}

int OkJ(int i, int j)
{
    if ( i < 1 || i > N || j < 1 || j > M ) return 0;
    if ( X[i][j] == 0 ) return 0;
    return 1;
}