Cod sursa(job #1758864)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 17 septembrie 2016 23:43:17
Problema Kdrum Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int MAXK = 12000;
const int MAXD = 72;
const int MAXN = 50;

int divider[1 + MAXD], position[1 + MAXK];
int a[1 + MAXN + 1][1 + MAXN + 1];
int dp[1 + MAXN][1 + MAXN][1 + MAXD];
int dividers = 0;

struct Element {
    int x;
    int y;
    int z;

    Element() {}

    Element(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
};

int Gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

queue<Element> Queue;

int line[4] = {0, 1, 0, -1};
int column[4] = {1, 0, -1, 0};

void BFS(int x, int y, int z, int k, int n, int m) {
    dp[x][y][z] = 1;
    Queue.push(Element(x, y, z));
    while (!Queue.empty()) {
        x = Queue.front().x;
        y = Queue.front().y;
        z = Queue.front().z;
        Queue.pop();
        for (int i = 0; i < 4; i++) {
            int x0 = x + line[i], y0 = y + column[i], z0 = position[Gcd(k, divider[z] * a[x0][y0])];
            if (x0 >= 1 && x0 <= n && y0 >= 1 && y0 <= m && a[x0][y0] && !dp[x0][y0][z0]) {
                dp[x0][y0][z0] = dp[x][y][z] + 1;
                Queue.push(Element(x0, y0, z0));
            }
        }
    }
}

int main() {
    int n, m, k, x1, y1, x2, y2;
    cin >> n >> m >> k >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= k; i++)
        if (k % i == 0) {
            dividers++;
            divider[dividers] = i;
            position[i] = dividers;
        }
    BFS(x1, y1, position[Gcd(k, a[x1][y1])], k, n, m);
    cout << dp[x2][y2][position[k]];
    return 0;
}