Pagini recente » Cod sursa (job #316049) | Cod sursa (job #2870974) | Cod sursa (job #1489946) | Cod sursa (job #1296347) | Cod sursa (job #264843)
Cod sursa(job #264843)
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <list>
#define pb push_back
using namespace std;
struct pozitie
{
int x, y, divz, pasi;
};
short dirI[] = {-1, 0, 0, 1};
short dirJ[] = {0, -1, 1, 0};
int n, m, k, x1, x2, y1, y2;
int matNr[60][60];
vector <int> matVizDiv[60][60];
list <pozitie> listBfs;
int gcd(int nr1, int nr2)
{
while (nr2)
{
int nrAux = nr1 % nr2;
nr1 = nr2;
nr2 = nrAux;
}
return nr1;
}
int findWay()
{
pozitie AUX;
AUX.x = x1;
AUX.y = y1;
AUX.divz = gcd(k, matNr[x1][y1]);
AUX.pasi = 1;
listBfs.pb(AUX);
for (; !listBfs.empty(); listBfs.pop_front())
{
int i = listBfs.front().x, j = listBfs.front().y;
if (i == x2 && j == y2 && listBfs.front().divz == k)
return listBfs.front().pasi;
for (int dir = 0; dir < 4; dir++)
{
if (i + dirI[dir] < 1 || i + dirI[dir] > n
|| j + dirJ[dir] < 1 || j + dirJ[dir] > m
|| !matNr[i + dirI[dir]][j + dirJ[dir]])
continue;
int ok = 1, divAj = gcd(listBfs.front().divz * matNr[i + dirI[dir]][j + dirJ[dir]], k);
for (int divi = 0; divi < matVizDiv[i + dirI[dir]][j + dirJ[dir]].size(); divi++)
if (divAj == matVizDiv[i + dirI[dir]][j + dirJ[dir]][divi])
{
ok = 0;
break;
}
if (ok)
{
AUX.x = i + dirI[dir];
AUX.y = j + dirJ[dir];
AUX.divz = divAj;
AUX.pasi = listBfs.front().pasi + 1;
listBfs.pb(AUX);
matVizDiv[i + dirI[dir]][j + dirJ[dir]].pb(divAj);
}
}
}
}
int main()
{
freopen("kdrum.in", "r", stdin);
freopen("kdrum.out", "w", stdout);
scanf("%d %d %d", &n, &m, &k);
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &matNr[i][j]);
if (matNr[i][j])
matNr[i][j] = gcd(matNr[i][j], k);
}
printf("%d\n", findWay());
fclose(stdin);
fclose(stdout);
return 0;
}