Cod sursa(job #2700629)

Utilizator PetyAlexandru Peticaru Pety Data 28 ianuarie 2021 11:58:16
Problema Kdrum Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <queue>
#include <algorithm>
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx,avx2,fma")


using namespace std;

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

struct nod {
  int x, y, d;
};
int dl[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};

int gcd (int a, int b) {
  while (b) {
    int r = a - a / b * b;
    a = b;
    b = r;
  }
  return a;
}

int n, m, k, dp[52][52][102], nrd[102], f[12002], v[52][52], nr, x1, y7, x2, y2;

int main()
{
  fin >> n >> m >> k;
  fin >> x1 >> y7 >> x2 >> y2;
  int i, j;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j)
      fin >> v[i][j];
  for (int i = 1; i <= k; ++i) {
    if (k / i == (k + i - 1) / i) {
      nrd[++nr] = i;
      f[i] = nr;
    }
  }
  queue<nod>q;
  q.push({x1, y7, f[__gcd(v[x1][y7], k)]});
  dp[x1][y7][f[__gcd(v[x1][y7], k)]] = 1;
  while (!q.empty()) {
    int x = q.front().x;
    int y = q.front().y;
    int d = q.front().d;
    q.pop();
    for (i = 0; i < 4; ++i) {
      int xx = x + dl[i];
      int yy = y + dc[i];
      if (v[xx][yy] != 0) {
        int poz = f[nrd[d] * __gcd(k / nrd[d], v[xx][yy])];
        if (dp[xx][yy][poz] == 0) {
          dp[xx][yy][poz] = dp[x][y][d] + 1;
          q.push({xx, yy, poz});
          if (xx == x2 && yy == y2 && poz == nr) {
            fout << dp[x2][y2][nr];
            return 0;
          }
        }
      }
    }
  }
  return 0;
}