Cod sursa(job #2514871)

Utilizator lucametehauDart Monkey lucametehau Data 27 decembrie 2019 11:00:34
Problema Kdrum Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

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

struct Nod {
  int x, y, ind;
};

int n, m, k, xs, ys, xf, yf;
int d;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int ind[12005];
int v[55][55], dp[55][55][80];
queue <Nod> q;

int main() {
  cin >> n >> m >> k >> xs >> ys >> xf >> yf;
  for(int i = 1; i <= k; i++) {
    if(k % i == 0)
      ind[i] = ++d;
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)
      cin >> v[i][j];
  }
  q.push({xs, ys, __gcd(v[xs][ys], k)});
  dp[xs][ys][ind[__gcd(v[xs][ys], k)]] = 1;
  while(!q.empty()) {
    Nod nod = q.front();
    q.pop();
    for(int i = 0; i < 4; i++) {
      int x = nod.x + dx[i], y = nod.y + dy[i];
      if(!v[x][y] || !x || x > n || !y || y > m)
        continue;
      int d = __gcd(nod.ind * v[x][y], k);
      if(!dp[x][y][ind[d]]) {
        dp[x][y][ind[d]] = dp[nod.x][nod.y][ind[nod.ind]] + 1;
        q.push({x, y, d});
      }
      if(dp[xf][yf][ind[k]]) {
        cout << dp[xf][yf][ind[k]];
        return 0;
      }
    }
  }
  return 0;
}