Cod sursa(job #1756777)

Utilizator Bodo171Bogdan Pop Bodo171 Data 13 septembrie 2016 17:20:36
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include<fstream>
#include<queue>
using namespace std;
struct type
{
    int l,c,div;
}el;
queue<type> q;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
int i,j,mx,d[55][55][75],a[55][55],n,m,k,div,v[75],ff,l1,c1,l2,c2,li,ci,nr,num,unu,doi,trei,x;
int cmmdc()
{
    unu=ff*num;
    doi=k;
    if(unu<doi) swap(unu,doi);
    while(doi!=0)
    {
        trei=unu%doi;
        unu=doi;
        doi=trei;
    }
    return unu;
}
int main()
{
    ifstream f("kdrum.in");
    ofstream g("kdrum.out");
    f>>n>>m>>k;
    f>>l1>>c1>>l2>>c2;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          f>>a[i][j];
    for(i=1;i<=k;i++)
      if(k%i==0)
      {
          nr++;
          v[nr]=i;
      }
    for(j=1;j<=nr;j++)
     if(a[l1][c1]%v[j]==0)
    {
    d[l1][c1][j]=1;
    el.div=1;el.l=1;el.c=j;q.push(el);
    }
    while(!q.empty())
    {
        num=q.front().div;
        li=q.front().l;
        ci=q.front().c;
        q.pop();
        for(i=0;i<4;i++)
        {
            el.l=li+d1[i];
            el.c=ci+d2[i];
            ff=1;
            if(a[el.l][el.c]!=0)
            {
                ff=a[el.l][el.c];
                x=cmmdc();
                for(j=1;v[j]<=x&&j<=nr;j++)
                {
                    if((num*ff)%v[j]==0)
                    {
                        if(d[el.l][el.c][v[j]]==0)
                        {
                            d[el.l][el.c][v[j]]=d[li][ci][num]+1;
                            el.div=v[j];
                            q.push(el);
                        }
                    }
                }
            }
         }

    }
    g<<d[l2][c2][k];
    return 0;
}