# Cod sursa(job #2437404)

Utilizator Data 9 iulie 2019 14:49:36 Kdrum 80 cpp-64 done Arhiva de probleme 2 kb
``````#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define x first
#define y second
#define Inf 6000
using namespace std;
int Ox[4]={-1, 0, 1, 0};
int Oy[4]={0, 1, 0, -1};
int n, m, k, area[52][52], dist[52][52][12001], cnt[12001], add, rev[12001], inc=1, fin;
struct trio{
int x, y, d;
};
trio q[1000000];
pair<int, int> start, finish;
void bfs();
int cmmdc(int a, int b);
int main()
{
freopen("kdrum.in", "r", stdin);
freopen("kdrum.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d%d%d", &start.x, &start.y, &finish.x, &finish.y);
for(int i=1; i<=k; ++i)
if(k%i==0){
if(cnt[i]) break;
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j) {
scanf("%d", &area[i][j]);
}
++fin;
q[fin]={start.x, start.y, cnt[cmmdc(max(k, area[start.x][start.y]), min(k, area[start.x][start.y]))]};
dist[start.x][start.y][cnt[cmmdc(max(k, area[start.x][start.y]), min(k, area[start.x][start.y]))]]=1;
bfs();
return 0;
}
void bfs(){
while(fin>=inc){
trio t=q[inc]; ++inc;
for(int i=0; i<4; ++i){
trio t1={t.x+Ox[i], t.y+Oy[i], cnt[cmmdc(max(k, rev[t.d]*area[t.x+Ox[i]][t.y+Oy[i]]), min(k, rev[t.d]*area[t.x+Ox[i]][t.y+Oy[i]]))]};
if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m || area[t1.x][t1.y]==0) continue;
if(dist[t.x][t.y][t.d]+1<dist[t1.x][t1.y][t1.d]){
dist[t1.x][t1.y][t1.d]=dist[t.x][t.y][t.d]+1;
if(finish==make_pair(t1.x, t1.y) && t1.d==cnt[k]) {printf("%d", dist[t1.x][t1.y][t1.d]); return;}
++fin;
q[fin]=t1;
}
}
}
return;
}
int cmmdc(int a, int b){
if(a==0 || b==0) return 1;
int d=a%b;
while(d!=0){
a=b; b=d; d=a%b;
}
return b;
}
``````