Cod sursa(job #1696449)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 aprilie 2016 02:47:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

const int DIM = 1 << 7;
const int INF = 0x3f3f3f3f;
using namespace std;

struct qnode{ int x, y; }; deque <qnode> my_queue;
char A[DIM][DIM]; int xst1, yst1, xst2, yst2, xfn;
int N, M, L, C, minim, yfn, Dp[2][DIM][DIM];

int Dx[9] = { 0, -1, -1, -1, 0, 1, 1, 1, 0 };
int Dy[9] = { 0, -1, 0, 1, 1, 1, 0, -1, -1 };

void BFS( int xst, int yst, int k ) {
    memset( Dp[k], INF, sizeof(Dp[k]) ); Dp[k][xst][yst] = 1;
    my_queue.clear(); my_queue.push_back( {xst, yst} );

    while( !my_queue.empty() ) {
        qnode node = my_queue.front();

        for( int d = 1; d <= 8; d ++ ) {
            qnode next_node = { node.x + Dx[d], node.y + Dy[d] };

            if( next_node.x < 1 || next_node.x > N ) continue;
            if( next_node.y < 1 || next_node.y > M ) continue;
            if( A[next_node.x][next_node.y] == 'X' ) continue;

            if( Dp[k][next_node.x][next_node.y] > Dp[k][node.x][node.y] + 1 ) {
                Dp[k][next_node.x][next_node.y] = Dp[k][node.x][node.y] + 1;
                my_queue.push_back( next_node );
            }
        }

        my_queue.pop_front();
    }

    return;
}

int main() {

    FILE *input_file  = fopen( "rj.in" , "r" );
    FILE *output_file = fopen( "rj.out", "w" );

    fscanf( input_file, "%d %d\n", &N, &M );

    for( int i = 1; i <= N; i ++ ) {
        fgets( A[i] + 1, DIM, input_file );

        for( int j = 1; j <= M; j ++ ) {
            if( A[i][j] == 'R' ) {
                xst1 = i;
                yst1 = j;
            }

            if( A[i][j] == 'J' ) {
                xst2 = i;
                yst2 = j;
            }
        }
    }

    BFS( xst1, yst1, 0 );
    BFS( xst2, yst2, 1 );

    minim = INF;
    for( int i = 1; i <= N; i ++ ) {
    for( int j = 1; j <= M; j ++ ) {
        if( Dp[0][i][j] == Dp[1][i][j] && Dp[0][i][j] < minim ) {
            minim = Dp[0][i][j];
            xfn = i;
            yfn = j;
        }
    }}

    fprintf( output_file, "%d %d %d\n", minim, xfn, yfn );

    return 0;
}