Cod sursa(job #2110170)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 20 ianuarie 2018 12:51:32
Problema Kdrum Scor 0
Compilator cpp Status done
Runda evaluare_cex_sv_cls_x_2 Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <deque>
std::ifstream f("kdrum.in");
std::ofstream g("kdrum.out");

struct nod {
    int y, x, p=0, left;
}n1, n2;
int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b, a%b);
} void calcul(nod &nd, int x) {
    nd.left = nd.left/gcd(nd.left, x);
}

int nr[55][55];
int N, M, K;
int y1, x1, y2, x2;
void citire() {
    f >> N >> M >> K;
    f >> n1.y >> n1.x >> n2.y >> n2.x;
    for (int i=1, j; i<=N; i++)
        for (j=1; j<=M; j++)
            f >> nr[i][j];
    n1.left = K;
}

bool viz[180][180];
int lee() {
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    std::deque <nod> q;
    q.push_front(n1);
    nod nou, pres;

    while(!q.empty()) {
        pres = q.back();
        q.pop_back();
        //std::cout << pres.y << ' ' << pres.x << ' ' << n2.y << ' ' << n2.x << '\n';
        //std::cin.get();

        if (pres.x == n2.x && pres.y == n2.y) {
            if(pres.left == 1)
                return pres.p;
        }

        for (int i=0; i<4; i++) {
            nou = pres; nou.p++;
            nou.x += dx[i]; nou.y += dy[i];

            if(nr[nou.y][nou.x] == 0);
            else {
                if(viz[nou.y][nou.x]) {
                    calcul(nou, nr[nou.y][nou.x]);
                    q.push_front(nou);
                } else {
                    calcul(nou, nr[nou.y][nou.x]);
                    viz[nou.y][nou.x] = 1;
                    q.push_back(nou);
                }
            }
        }
    }
}


int main()
{
    citire();
    g << lee()+1;

    return 0;
}