Cod sursa(job #1764895)

Utilizator GinguIonutGinguIonut GinguIonut Data 26 septembrie 2016 08:01:31
Problema Kdrum Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <queue>

#define nMax 52
#define mMax 52
#define divMax 150
#define kMax 12001
#define pii pair<int, int>
#define piii pair<pii, int>
#define x first
#define y second
#define mkp make_pair

using namespace std;

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

int n, m, MOD, lStart, lFinal, cStart, cFinal, nrDiv;
int divisors[divMax], viz[kMax], mat[nMax][mMax], dp[nMax][mMax][divMax];
int dx[]={1, 0, -1, 0};
int dy[]={0, 1, 0, -1};
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];
}

void compute_divisors()
{
    divisors[++nrDiv]=0;
    viz[0]=nrDiv;

    for(int i=1; i<=MOD/2; i++)
    {
        if(i==mat[lStart][cStart]%MOD)
        {
            viz[mat[lStart][cStart]%MOD]=++nrDiv;
            divisors[nrDiv]=mat[lStart][cStart]%MOD;
            continue;
        }

        if(MOD%i==0)
        {
            viz[i]=++nrDiv;
            divisors[nrDiv]=i;
        }
    }
}

void solve()
{
    compute_divisors();
    dp[lStart][cStart][viz[mat[lStart][cStart]%MOD]]=1;

    for(Q.push(mkp(mkp(lStart, cStart), viz[mat[lStart][cStart]%MOD])); !Q.empty(); )
    {
        int lin=Q.front().x.x;
        int col=Q.front().x.y;
        int val=Q.front().y;
        Q.pop();

        for(int i=0; i<4; i++)
        {
            int lFin=lin+dx[i];
            int cFin=col+dy[i];

            if(mat[lFin][cFin] && lFin<=n && lFin>0 && cFin<=m && cFin>0)
            {
                int newVal=(divisors[val]*mat[lFin][cFin])%MOD;

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

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

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