# Cod sursa(job #2450657)

Utilizator Data 23 august 2019 23:31:22 Kdrum 100 cpp-32 done Arhiva de probleme 2.79 kb
``````#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

ifstream f("kdrum.in");
ofstream g("kdrum.out");

int n, m, k, a[52][52], expo[7][52][52];

int ctd, nrd[12002], divi[102], prim[7], exxp[7], nrp, put[7][20];

bool viz[52][52][102];
int mindist[52][52][102];

int xa, ya, xb, yb, ox[] = {-1, 0, 1, 0}, oy[] = {0, 1, 0, -1};

void factorization()
{
for(int i = 1; i <= k; ++i)
if(k % i == 0)
++ctd, nrd[i] = ctd, divi[ctd] = i;
for(int i = 2; i <= k; ++i)
if(k % i == 0)
{
++nrp;
prim[nrp] = i;
put[nrp][0] = 1;
while(k % i == 0)
k /= i, ++exxp[nrp], put[nrp][exxp[nrp]] = put[nrp][exxp[nrp] - 1] * i;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int q = 1; q <= nrp; ++q)
{
if(a[i][j] == 0)
continue;
int x = 0;
while(a[i][j] % prim[q] == 0)
a[i][j] /= prim[q], ++x;
x = min(x, exxp[q]);
expo[q][i][j] = x;
}

}

void bfs()
{
int product = 1;
for(int i = 1; i <= nrp; ++i)
for(int j = 1; j <= expo[i][xa][ya]; ++j)
product *= prim[i];
viz[xa][ya][nrd[product]] = 1;
mindist[xa][ya][nrd[product]] = 1;
deque<pair<pair<int, int>, int> >d;
d.push_back({{xa, ya}, nrd[product]});
while(!d.empty())
{
pair<pair<int, int>, int> nod = d[0];
d.pop_front();
for(int i = 0; i <= 3; ++i)
{
int new_x = nod.fi.fi + ox[i];
int new_y = nod.fi.se + oy[i];
if(a[new_x][new_y] == 0)
continue;
int new_product = divi[nod.se];
for(int pdiv = 1; pdiv <= nrp; ++pdiv)
for(int jj = 1; jj <= expo[pdiv][new_x][new_y]; ++jj)
{
new_product *= prim[pdiv];
if(new_product > 12000 || !nrd[new_product])
{
new_product /= prim[pdiv];
break;
}
}
if(!viz[new_x][new_y][nrd[new_product]])
{
d.push_back({{new_x, new_y}, nrd[new_product]});
viz[new_x][new_y][nrd[new_product]] = 1;
mindist[new_x][new_y][nrd[new_product]] = mindist[nod.fi.fi][nod.fi.se][nod.se] + 1;
}
}
}
}

int main()
{
f >> n >> m >> k;
f >> xa >> ya >> xb >> yb;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
f >> a[i][j];

factorization();

bfs();

g << mindist[xb][yb][ctd];

return 0;
}
``````