Cod sursa(job #1766022)

Utilizator GinguIonutGinguIonut GinguIonut Data 27 septembrie 2016 12:03:35
Problema Kdrum Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <vector>
#include <queue>

#define nMax 52
#define mMax 52
#define divMax 150
#define valMax 100001
#define INF 30001
#define pb push_back
#define mkp make_pair
#define x first
#define y second
#define pii pair<short int, short int>
#define piii pair<pii, short int>

using namespace std;

ifstream fin("kdrum.in");
ofstream fout("kdrum.out");

int n, m, MOD, nrDiv, lStart, cStart, lFinal, cFinal;
int dx[]={1, 0, -1, 0};
int dy[]={0, 1, 0, -1};
int mat[nMax][mMax];
short int seen[valMax], divisors[divMax], dp[nMax][mMax][divMax], gcd[nMax][mMax][divMax];
bool viz[nMax][mMax][divMax];
queue<piii> Q;

void read()
{
    fin>>n>>m>>MOD;
    fin>>lStart>>cStart>>lFinal>>cFinal;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            fin>>mat[i][j];
}

int _gcd(int a, int b)
{
    int r=a%b;

    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }


    return b;
}

void compute_divisors()
{
    for(int i=1; i<=MOD; i++)
    {
        if(MOD%i==0)
        {
            divisors[++nrDiv]=i;
            seen[i]=nrDiv;
        }
    }
}

void solve()
{
    compute_divisors();

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            for(int k=1; k<=nrDiv; k++)
            {
                gcd[i][j][k]=_gcd(mat[i][j]*divisors[k], MOD);
                dp[i][j][k]=INF;
            }
        }
    }

    dp[lStart][cStart][seen[gcd[lStart][cStart][1]]]=1;
    for(Q.push(mkp(mkp(lStart, cStart), seen[gcd[lStart][cStart][1]])); !Q.empty(); )
    {
        int lin=Q.front().x.x;
        int col=Q.front().x.y;
        int val=Q.front().y;
        Q.pop();
        viz[lin][col][val]=0;

        for(int i=0; i<4; i++)
        {
            int lFin=lin+dx[i];
            int cFin=col+dy[i];
            if(lFin>=1 && lFin<=n && cFin>=1 && cFin<=m && mat[lFin][cFin])
            {
                int newVal=_gcd(gcd[lFin][cFin][val], MOD);

                if(dp[lFin][cFin][seen[newVal]]>dp[lin][col][val]+1)
                {
                    dp[lFin][cFin][seen[newVal]]=dp[lin][col][val]+1;
                    if(viz[lFin][cFin][seen[newVal]]==0)
                    {
                        viz[lFin][cFin][seen[newVal]]=1;
                        Q.push(mkp(mkp(lFin, cFin), seen[newVal]));
                    }
                }
            }
        }
    }
}

void write()
{
    fout<<dp[lFinal][cFinal][nrDiv];
}

int main()
{
    read();
    solve();
    write();
}