Cod sursa(job #1712826)

Utilizator Athena99Anghel Anca Athena99 Data 3 iunie 2016 20:06:26
Problema Kdrum Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int nmax= 50;
const int pmax= 12000;
const int divmax= 72;
const int dx[]= {0, 0, 1, -1};
const int dy[]= {1, -1, 0, 0};

int n, m, k;
int v[nmax+2][nmax+2], w[divmax+1], f[pmax+1], d[nmax+1][nmax+1][divmax+1];

struct str {
    int x, y, z;
};

inline str mp( int x, int y, int z ) {
    str sol;
    sol.x= x, sol.y= y, sol.z= z;

    return sol;
}

int gcd( int x, int y ) {
    if ( y==0 )
        return x;
    return gcd(y, x%y);
}

void bfs( int x, int y, int z ) {
    d[x][y][z]= 1;
    queue <str> q;
    for ( q.push(mp(x, y, z)); !q.empty(); q.pop() ) {
        x= (q.front()).x, y= (q.front()).y, z= (q.front()).z;
        for ( int l= 0; l<4; ++l ) {
            int a= x+dx[l], b= y+dy[l], c= f[gcd(k, w[z]*v[a][b])];
            if ( a>=1 && a<=n && b>=1 && b<=m && v[a][b]!=0 && d[a][b][c]==0 ) {
                d[a][b][c]= d[x][y][z]+1;
                q.push(mp(a, b, c));
            }
        }
    }
}

int main(  ) {
    int x1, y1, x2, y2;
    fin>>n>>m>>k>>x1>>y1>>x2>>y2;
    for ( int i= 1, j= 0; i<=k; ++i ) {
        if ( k%i==0 ) {
            ++j;
            f[i]= j;
            w[j]= i;
        }
    }
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>v[i][j];
        }
    }

    bfs(x1, y1, f[gcd(k, v[x1][y1])]);
    fout<<d[x2][y2][f[k]];

    return 0;
}