Cod sursa(job #1011937)

Utilizator dd1997Dan Vasile dd1997 Data 17 octombrie 2013 19:32:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <cstdlib>

using namespace std;


ifstream f ("rj.in");
ofstream g ("rj.out");

int m, n, i, k, c, fx, fy, xjuli, yjuli,j;
char ch;
int vx [] = {1, 1, 0, -1, -1, -1, 0, 1};
int vy [] = {0, 1, 1, 1, 0, -1, -1, -1};
queue <short int> x;
queue <short int> y;

int main()
{
   f >> n >> m;
   //cout << n << ' ' << m << endl;
   short int romeo[n+2][m+2], julietta[n+2][m+2], labirint[n+2][m+2] ;
   for (i=0;i<=n+1;i++)
      for (j=0;j<=m+1;j++)
      {
         romeo[i][j] = julietta[i][j] = n*m+10;
         labirint[i][j] = 0;
      }

    for (i=0;i<=n+1;i++)
       labirint[i][0] = labirint[i][m+1] = -5;
    for (i=0;i<=m+1;i++)
       labirint[0][i] = labirint[n+1][i] = -5;

   string s;
   getline(f, s);

   for (i = 1; i <= n; i++)
   {
       getline(f, s);
       //cout << s << endl;
       for (k = 1; k <= m; k++)
       {
           ch = s[k-1];
           //cout << ch << ' ';
           switch (ch)
           {
           case 'X':
               labirint[i][k] = -5;
               break;
           case 'R':
               x.push(i);
               y.push(k);
               romeo[i][k] = 1;
               break;
           case 'J':
               xjuli = i;
               yjuli = k;
               //cout << i << ' ' << k << endl;
               break;
           }
       }
   }
/*
    for (i=0;i<=n+1;i++)
    {
      for (j=0;j<=m+1;j++)
         cout << labirint[i][j]<<' ';
    cout << endl;
      }
*/
   c = 1;

   while(x.size()>0)
   {
       int xc = x.front();
       int yc = y.front();
       //cout << ' '<<x.front()<<' '<<y.front()<<endl;
       x.pop();
       y.pop();

       for (i = 0; i < 8; i++)
       {
           int xu = xc+vx[i], yu = yc+vy[i];
           //cout << romeo[xu][yu] << ' ' << romeo[xc][yc] << endl;
           if((labirint[xu][yu]==0)&&romeo[xu][yu] > romeo[xc][yc] + 1)
           {
               romeo[xu][yu] = romeo[xc][yc] + 1;
               x.push(xu);
               y.push(yu);
            }
       }
   }
   x.push(xjuli);
   y.push(yjuli);
   julietta[xjuli][yjuli] = 1;
   while(x.size()>0)
   {
       int xc = x.front();
       int yc = y.front();
       //cout << ' '<<x.front()<<' '<<y.front()<<endl;
       x.pop();
       y.pop();
       for (i = 0; i < 8; i++)
       {
           int xu = xc+vx[i], yu = yc+vy[i];
           if((labirint[xu][yu]==0)&&julietta[xu][yu] > julietta[xc][yc] + 1)
           {
               julietta[xu][yu] = julietta[xc][yc] + 1;
               x.push(xu);
               y.push(yu);
            }
       }
   }
/*
    for (i=0;i<=n+1;i++)
    {
      for (j=0;j<=m+1;j++)
         cout << romeo[i][j]<<' ';
    cout << endl;
      }
    cout << endl << endl;
    for (i=0;i<=n+1;i++)
    {
      for (j=0;j<=m+1;j++)
         cout << julietta[i][j]<<' ';
    cout << endl;
      }
      */
   int minim = n*m+100;
   for (i=1;i<=n;i++)
     for (j=1;j<=m;j++)
        if (romeo[i][j] == julietta[i][j])
           if (romeo[i][j] < minim)
             {
                 minim = romeo[i][j];
                 fx = i;
                 fy = j;
             }
   g <<minim << ' '<< fx << " " << fy << endl;
   return 0;
}