Cod sursa(job #189690)

Utilizator fogabFodor Gabor fogab Data 17 mai 2008 05:49:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

#define LL long long
#define ULL unsigned long long
#define PB push_back
#define x first
#define y second

using namespace std;

typedef pair<int,int> P;

char m[110][110];
map <P, int> val;
queue <P> stack;

int main(void){

    ifstream in("rj.in");
    ofstream out("rj.out");
    
    int i,j,N,M;
    char C;
    P R,J;
    
    
    in >> N >> M;
    in.getline(m[0],0);
    
    for (i=0;i<N;i++)
    {
        in.getline(m[i],110);
        for (j=0;j<M;j++)
        {
            if (m[i][j]=='R') {R.x = i;R.y = j;}
            if (m[i][j]=='J') {J.x = i;J.y = j;}
        }
    }        
    
    stack.push(R);
    val[R] = 1;
    
    P Z(-1,-1);
    int r;
    
    while (Z != J)
    {
       Z = stack.front();
       stack.pop();
       r = val[Z];
       //out << Z.x << " " << Z.y << " " << r <<"\n";
       
       if (Z.x > 0  && m[Z.x-1][Z.y]!='X' && val.count(P(Z.x-1,Z.y)) == 0)
       {
          stack.push(P(Z.x-1,Z.y));
          val[P(Z.x-1,Z.y)] = r+1;
       }
       if (Z.y > 0  && m[Z.x][Z.y-1]!='X' && val.count(P(Z.x,Z.y-1)) == 0)
       {
          stack.push(P(Z.x,Z.y-1));
          val[P(Z.x,Z.y-1)] = r+1;
       }
       if (Z.x <N-1  && m[Z.x+1][Z.y]!='X' && val.count(P(Z.x+1,Z.y)) == 0)
       {
          stack.push(P(Z.x+1,Z.y));
          val[P(Z.x+1,Z.y)] = r+1;
       }
       if (Z.y <M-1  && m[Z.x][Z.y+1]!='X' && val.count(P(Z.x,Z.y+1)) == 0)
       {
          stack.push(P(Z.x,Z.y+1));
          val[P(Z.x,Z.y+1)] = r+1;
       }                     
         
    }
    P sol(999,999);
    int max= val[J];
    r = max;
    out << max/2 << " ";
    
    Z = J;
    
    while (r!=1)
    {
       if (Z.x > 0  && val.count(P(Z.x-1,Z.y)) != 0 && val[P(Z.x-1,Z.y)] == r-1)
       {
          Z.x--;r--;
          int dist = max+1 - 2*r;
          if (abs( dist ) <2)
             sol = Z;
       }
       if (Z.y > 0  && val.count(P(Z.x,Z.y-1)) != 0 && val[P(Z.x,Z.y-1)] == r-1)
       {
          Z.y--;r--;
          int dist = max+1 - 2*r;
          if (abs( dist ) <2)
             sol = Z;
       }
       if (Z.x <N-1 && val.count(P(Z.x+1,Z.y)) != 0 && val[P(Z.x+1,Z.y)] == r-1)
       {
          Z.x++;r--;
          int dist = max+1 - 2*r;
          if (abs( dist ) <2)
             sol = Z;
       }
       if (Z.y <M-1 && val.count(P(Z.x,Z.y+1)) != 0 && val[P(Z.x,Z.y+1)] == r-1)
       {
          Z.y++;r--;
          int dist = max+1 - 2*r;
          if (abs( dist ) <2)
             sol = Z;
       }                                      
    }
    
    out << sol.x+1 << " " << sol.y+1;
    
    in.close();
    out.close();

return 0;
}