Mai intai trebuie sa te autentifici.

Cod sursa(job #2013448)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 21 august 2017 14:53:45
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

const int MAXN = (int) 50;
const int SQRT = (int) 110;
const int MAXK = (int) 12000;

int mat[MAXN + 2][MAXN + 2];

inline int gcd(int a, int b) {
    int r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

const int MAXQ = (int) (1 << 19);

struct Cell {
    int l, c;
    int val;
    int dst;
}q[MAXQ];

char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};

inline void mod(int &x) {
    x &= (MAXQ - 1);
}

int main() {
    FILE *fi, *fout;
    int i, n, m, k, x1, y1, x2, y2, j;
    fi = fopen("kdrum.in" ,"r");
    fout = fopen("kdrum.out" ,"w");
    fscanf(fi,"%d %d %d " ,&n,&m,&k);
    fscanf(fi,"%d %d %d %d " ,&x1,&y1,&x2,&y2);
    for(i = 1; i <= n; i++)
       for(j = 1; j <= m; j++)
           fscanf(fi,"%d " ,&mat[i][j]);
    int b = 0, e = 1;
    q[0] = {x1, y1, gcd(mat[x1][y1], k), 1};
    do {
        for(i = 0; i < 4; i++) {
            int l = q[b].l + dl[i];
            int c = q[b].c + dc[i];
            if(mat[l][c] > 0) {
                int val = gcd(q[b].val * mat[l][c], k);
                q[e++] = {l, c, val, q[b].dst + 1};
                if(l == x2 && c == y2 && val == k) {
                    fprintf(fout,"%d" ,q[b].dst + 1);
                    return 0;
                }
                mod(e);
            }
        }
        b++;
        mod(b);
    }while(b < e);
    fclose(fi);
    fclose(fout);
    return 0;
}