Cod sursa(job #2013498)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 21 august 2017 16:21:21
Problema Kdrum Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 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;
}q[MAXQ];

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

int dp[MAXN + 1][MAXN + 1][2 * SQRT + 1];

int dv[2 * SQRT + 1];
int ind[MAXK + 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 cnt = 0;
    for(i = 1; i <= k; i++)
       if(k % i == 0) {
            dv[++cnt] = i;
            ind[i] = cnt;
       }
    int b = 0, e = 1;
    q[0] = {x1, y1, ind[gcd(mat[x1][y1], k)]};
    dp[x1][y1][ind[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 = ind[gcd(dv[q[b].val] * mat[l][c], k)];
                if(dp[l][c][val] == 0 || dp[l][c][val] > dp[q[b].l][q[b].c][q[b].val] + 1) {
                    q[e++] = {l, c, val};
                    dp[l][c][val] = dp[q[b].l][q[b].c][q[b].val] + 1;
                }
            }
        }
        b++;
    }while(b < e);
    fprintf(fout,"%d" ,dp[x2][y2][ind[k]]);
    fclose(fi);
    fclose(fout);
    return 0;
}