Cod sursa(job #1110216)

Utilizator dtz.petricanPetrican Danut dtz.petrican Data 17 februarie 2014 21:26:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
#include <queue>
#include <string>
 
using namespace std ;
 
const int NMAX = 105 ;
const int INF = 0x3f3f3f3f;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1 } ;
const int dy[] = {-1, 0 , 1, -1, 1, -1, 0, 1 } ;
string s ;
 
ifstream cin("rj.in") ;
ofstream cout("rj.out") ;
 
int N, M, C[NMAX][NMAX], D[NMAX][NMAX], B[NMAX][NMAX];
queue <pair <int, int>  > Q ;
int sol = INF;
short  cx[3], cy[3];
 int K =0  ;
 
void lee(int D[NMAX][NMAX],  int xi,  int yi)
{
    Q.push(make_pair(xi, yi)) ;
    D[xi][yi] = 1 ;
    while(!Q.empty())
    {
        int x = Q.front().first ;
       int y = Q.front().second ;
        Q.pop() ;
        for(int i = 0 ; i < 8 ; ++ i)
        {
             int xnou = x + dx[i] ;
           int ynou = y + dy[i] ;
            if(xnou >= 1 && xnou <= N && ynou >= 1 && ynou <= M)
              if(D[xnou][ynou] == 0)  {
                    D[xnou][ynou] = D[x][y] + 1 ;
                    Q.push(make_pair(xnou, ynou)) ;
                }
        }
    }
}
 
 
 
void citire()
{
    cin >> N >> M;
    getline(cin,s);
 
    for( int i = 1 ; i <= N ; ++ i)
    {
        getline(cin,s);
        for( int j = 0 ; j < M ; ++ j)
            if(s[j] == ' ') D[i][j+1] = 0 ;
            else if(s[j] == 'X' ) D[i][j+1] = -1 ;
            else if(s[j] == 'R' || s[j] == 'J')
            {
                D[i][j+1]=0;
                cx[ ++K ] = i;
                cy[ K ] = j+1;
            }
    }
 
    for( int i = 1; i <= N ; ++ i)
        for( int j = 1 ; j <= M ; ++ j)
        {
            B[i][j] = D[i][j];
            C[i][j] = D[i][j];
        }
}
void afisare()
{
    for( int i = 1 ; i <= N; ++i)
        for( int j = 1 ; j <= M ; ++ j)
            if(B[i][j] > 0 && B[i][j] == C[i][j] && B[i][j] < sol)
            {
                sol = B[i][j] ;
                cx[1] = i ;
                cy[1] = j ;
            }
    cout << sol << ' ' << cx[1] << ' ' <<cy[1]  << '\n' ;
}
 
int main()
{
    citire() ;
 
    lee(B, cx[1], cy[1]) ;
    lee(C, cx[2], cy[2]) ;
 
    afisare() ;
    cin.close() ;
    cout.close() ;
    return 0;
}