Cod sursa(job #2131233)

Utilizator inquisitorAnders inquisitor Data 14 februarie 2018 16:02:45
Problema Kdrum Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

int L, C, K, x2, y2, park[51][51], visited[51][51];

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};

int BFS(pair<int, int> start)
{
    queue<pair<int, int> > q; q.push(start);

    visited[start.first][start.second] = 1;

    while(!q.empty())
    {
        int i = q.front().first,
            j = q.front().second;

        q.pop();

        while(__gcd(park[i][j], K) != 1)
        {
            K /= __gcd(park[i][j], K);
        }

        if(K == 1 && i == x2 && j == y2)
        {
            return visited[i][j];
        }

        for(int d = 0; d < 4; d++)
        {
            int I = i + dx[d], J = j + dy[d];

            if(I < 1 | I > L | J < 1 | J > C | visited[I][J] | !park[I][J])
            {
                continue;
            }

            q.push({I, J});

            visited[I][J] = visited[i][j] + 1;
        }
    }
}

int main()
{
    freopen("kdrum.in", "r", stdin);
    freopen("kdrum.out", "w", stdout);

    int x1, y1;

    scanf("%d %d %d %d %d %d %d", &L, &C, &K, &x1, &y1, &x2, &y2);

    for(int i = 1; i <= L; i++)
    {
        for(int j = 1; j <= C; j++)
        {
            scanf("%d", &park[i][j]);
        }
    }

    printf("%d", BFS({x1, y1}));

    return 0;
}