Cod sursa(job #2437382)

Utilizator CharacterMeCharacter Me CharacterMe Data 9 iulie 2019 13:55:32
Problema Kdrum Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 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, rev[12001];
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;
            cnt[i]=++add; rev[add]=i;
            cnt[k/i]=++add; rev[add]=k/i;
        }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j) {
           scanf("%d", &area[i][j]);
           for(int k=1; k<=add; ++k) dist[i][j][k]=Inf;
    }
    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) && t.d==cnt[k]) {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, 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;
                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);
}