Cod sursa(job #2067843)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 noiembrie 2017 21:26:45
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("kdrum.in");
ofstream fout("kdrum.out");
int n, m, k, xi, yi, xf, yf, a[52][52], coada[500002][4], dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
int cmmdc(unsigned long long p, unsigned long long q)
{
    unsigned long long r=p%q;
    while(r)
    {
        q=p;
        p=r;
        r=p%q;
    }
    return (int)q;
}
void lee()
{
    int i, x, y, xx, yy, p, u;
    p=u=1;
    coada[1][0]=xi;
    coada[1][1]=yi;
    coada[1][2]=cmmdc(a[xi][yi],k);
    coada[1][3]=1;
    while(p<=u)
    {
        x=coada[p][0];
        y=coada[p][1];
        for(i=0; i<=3; i++)
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(1<=xx && xx<=n && 1<=yy && yy<=n && a[xx][yy]!=-1)
            {
                u++;
                coada[u][0]=xx;
                coada[u][1]=yy;
                coada[u][2]=cmmdc((unsigned long long)(coada[u][2]*a[xx][yy]),(unsigned long long)k);
                coada[u][3]=coada[p][3]+1;
                if(xx==xf && yy==yf && coada[u][2]==k)
                {
                    fout<<coada[u][3]<<'\n';
                    return;
                }
            }
        }
        p++;
    }
}
int main()
{
    int i, j;
    fin>>n>>m>>k>>xi>>yi>>xf>>yf;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fin>>a[i][j];
            if(!a[i][j])
                a[i][j]=-1;
        }
    lee();
    return 0;
}