Cod sursa(job #1734910)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 28 iulie 2016 15:15:13
Problema Kdrum Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "kdrum.in"  );
ofstream out( "kdrum.out" );

const int DIM = 52;
const int DIM2 = 202;
const int INF = 0x3f3f3f3f;

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int N, M, K, X1, Y1, X2, Y2, P, a[DIM][DIM], inQ[DIM][DIM][DIM2];
int dp[DIM][DIM][DIM2], d[DIM2], pos[DIM2 * 60];
struct str{ int x, y, z; }; deque <str> myQ;

int gcd( int X, int Y ) {
    return !Y ? X : gcd( Y, X % Y );
}

int main() {

    in >> N >> M >> K;
    in >> X1 >> Y1 >> X2 >> Y2;

    for( int i = 1; i <= N; i ++ )
    for( int j = 1; j <= M; j ++ )
        in >> a[i][j];

    for( int i = 1; i <= K; i ++ ) {
        if( K % i == 0 ) {
            d[++P] = i;
            pos[i] = P;
        }
    }

    memset( dp, INF, sizeof(dp) );
    dp [ X1 ][ Y1 ][ pos[ gcd( a[X1][Y1], K ) ] ] = 1;
    inQ[ X1 ][ Y1 ][ pos[ gcd( a[X1][Y1], K ) ] ] = 1;
    myQ.push_back( { X1, Y1, pos[ gcd( a[X1][Y1], K ) ] } );

    while( !myQ.empty() ) {
        str node = myQ.front();

        for( int l = 0; l < 4; l ++ ) {
            int X = node.x + dx[l];
            int Y = node.y + dy[l];

            if( X < 1 || X > N ) continue;
            if( Y < 1 || Y > M ) continue;
            if( a[X][Y] == 0 ) continue;

            if( dp[X][Y][ pos[ gcd( d[node.z] * a[X][Y], K ) ] ] > dp[ node.x ][ node.y ][ node.z ] + 1 ) {
                dp[X][Y][ pos[ gcd( d[node.z] * a[X][Y], K ) ] ] = dp[ node.x ][ node.y ][ node.z ] + 1;

                if( inQ[X][Y][ pos[ gcd( d[node.z] * a[X][Y], K ) ] ] == 0 ) {
                    inQ[X][Y][ pos[ gcd( d[node.z] * a[X][Y], K ) ] ] = 1;
                    myQ.push_back( { X, Y, pos[ gcd( d[node.z] * a[X][Y], K ) ] } );
                }
            }
        }

        inQ[ node.x ][ node.y ][ node.z ] = 0;
        myQ.pop_front();
    }

    out << dp[X2][Y2][P] << "\n";

    return 0;
}