Cod sursa(job #107994)

Utilizator TabaraTabara Mihai Tabara Data 20 noiembrie 2007 23:45:59
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <fstream>
using namespace std;

#define in "rj.in"
#define out "rj.out"
#define NMAX 101
#define INF 32000

char a[NMAX][NMAX];
typedef int MATR[NMAX][NMAX];
MATR mr;//matricea ROMEO
MATR mj;//matricea JULIETA
int c[NMAX*NMAX][2];
int n, m;
int prim, ultim;
int tmin;
int imin, jmin, iv, jv, is, js, ir, jr, ij, jj;

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

void Read();
void LeeR();
void LeeJ();
void Write();
int Ok(int,int);
int Ok1(int,int);
void Write();

int main()
{
    Read();
    LeeR();
    LeeJ();
    Write();
    
    return 0;
}

void Read()
{
	ifstream fin("rj.in");
	fin >> m >> n;
	int i, j;
	fin.get();
	for ( i = 1; i <= m; i++ )
	{
		for ( j = 1; j <= n; j++ )
		{
			a[i][j] = fin.get();
			if ( a[i][j] == 'R' ) ir = i, jr = j;
			if ( a[i][j] == 'J' ) ij = i, jj = j;
			mr[i][j] = mj[i][j] = INF;
		}
		fin.get();   // citeste Enter
	}
     for ( i = 0; i <= m + 1; i++)
         mr[i][0] = mr[i][n+1] = mj[i][0] = mj[i][n+1] = INF;
     for ( j = 0; j <= n + 1; j++)
         mr[0][j] = mr[m+1][j] = mj[0][j] = mj[m+1][j] = INF;
     mr[ir][jr] = 0;
     mj[ij][jj] = 0;
     fin.close();
}

void LeeR()
{
     int i, j, d;
     prim = ultim = 0;
     c[prim][0] = ir;
     c[prim][1] = jr;
     mr[ir][jr] = 0;
     while ( prim <= ultim )
     {
           for ( d = 0; d < 8; d++)
           {
               i = c[prim][0];
               j = c[prim][1];
               iv = i + di[d];
               jv = j + dj[d];
               if (Ok(iv,jv))
               {
                             if ( mr[iv][jv] > mr[i][j] + 1)
                             {
                                  mr[iv][jv] = mr[i][j] + 1;
                                  ultim++;
                                  c[ultim][0] = iv;
                                  c[ultim][1] = jv;
                             }
               }
           }
           prim++;
     }
}

int Ok(int i, int j)
{
    if ( i < 1 || i > m || j < 1 || j > n) return 0;
    if ( a[i][j] == 'X') return 0;
    if (  mr[i][j] < INF ) return 0;
    return 1;
}

int Ok1(int i, int j)
{
    if ( i < 1 || i > m || j < 1 || j > n) return 0;
    if ( a[i][j] == 'X') return 0;
    if (  mj[i][j] < INF ) return 0;
    return 1;
}
            
void LeeJ()
{
     int i, j, d;
     prim = ultim = 0;
     c[prim][0] = ij;
     c[prim][1] = jj;
     mj[ij][jj] = 0;
     while ( prim <= ultim )
     {
           for ( d = 0; d < 8; d++)
           {
               i = c[prim][0];
               j = c[prim][1];
               iv = i + di[d];
               jv = j + dj[d];
               if ( Ok1(iv,jv))
               {
                    if (mj[iv][jv] > mj[i][j] + 1)
                    {
                                  mj[iv][jv] = mj[i][j] + 1;
                                  ultim++;
                                  c[ultim][0] = iv;
                                  c[ultim][1] = jv;
                    }
               }
           }
           prim++;
     }
}
               
                                                     
void Write()
{
     ofstream fout ( out );
     int i, j;
     /*for ( i = 1; i <= m; i++)
     {
         for ( j = 1; j <= n; j++)
             fout << mr[i][j] << " ";
         fout << "\n";
     }
     fout << "\n";
     for ( i = 1; i <= m; i++)
     {
         for ( j = 1; j <= n; j++)
             fout << mj[i][j] << " ";
         fout << "\n";
     }
     fout << "\n";
     
     fout << ir << " " << jr << " " << ij << " " << jj << "\n";*/
     tmin = INF; 
     for ( i = 1; i <= m; i++)
         for ( j = 1; j <= n; j++)
             if ( mr[i][j] == mj[i][j])
                if ( mr[i][j] < tmin )
                {
                     tmin = mr[i][j] + 1;
                     imin = i;
                     jmin = j;
                }
     fout << tmin << " " << imin << " " << jmin << "\n";
     fout.close();
}