Cod sursa(job #2437372)

Utilizator Data 9 iulie 2019 13:41:14 Kdrum 20 cpp-64 done Arhiva de probleme 1.87 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]={0, 1, 0, -1};
int Oy[4]={1, 0, -1, 0};
int n, m, k, area[52][52], dist[52][52][12001], cnt[12001], add;
struct trio{
int x, y, d;
};
queue<trio> q;
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]);
}
q.push({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(!q.empty()){
trio t=q.front(); q.pop();
if(finish==make_pair(t.x, t.y)) {printf("%d", dist[t.x][t.y][t.d]); return;}
for(int i=0; i<4; ++i){
trio t1={t.x+Ox[i], t.y+Oy[i], cnt[cmmdc(max(k, t.d*area[t.x+Ox[i]][t.y+Oy[i]]), min(k, 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;
q.push(t1);
}
}
}
return;
}
int cmmdc(int a, int b){
if(a==0 || b==0) return 1;
if(a%b==0) return b;
int d=a%b;
return cmmdc(b, d);
}
``````