Cod sursa(job #2110188)

Utilizator SCatalinStanciu Catalin SCatalin Data 20 ianuarie 2018 12:56:49
Problema Kdrum Scor 20
Compilator cpp Status done
Runda evaluare_cex_sv_cls_x_2 Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

long long v[100][100],nr[100][100],fin[100][100];
int n,m;
int diri[] = {1,-1,0,0};
int dirj[] = {0,0,1,-1};
const int INF = INT_MAX;

struct triple
{
    int a,b;
    long long c;
};
bool inside(int i, int j)
{
    return (i>=1 && i<=n && j>=1 && j<=m);
}

int main()
{
    int x1,y1,x2,y2,K;
    in >> n >> m >> K >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=m; j++)
        {
            in >> v[i][j];
            nr[i][j] = fin[i][j] = INF;
        }
    queue <triple> Q;
    nr[x1][y1] = 1;
    Q.push({x1,y1,v[x1][y1]});
    while (!Q.empty())
    {
        int i = Q.front().a;
        int j = Q.front().b;
        long long prod = Q.front().c;
        for (int k = 0; k<4; k++)
        {
            int i2 = i+diri[k];
            int j2 = j+dirj[k];
            if (inside(i2,j2) && v[i2][j2]>0)
            {
                if (prod*v[i2][j2]%K == 0 && nr[i][j]+1<fin[i2][j2])
                {
                    fin[i2][j2] = nr[i][j]+1;
                    nr[i2][j2] = nr[i][j]+1;
                    Q.push({i2,j2,prod*v[i2][j2]});
                }
                else if (fin[i2][j2]>nr[i][j]+1)
                {
                    Q.push({i2,j2,prod*v[i2][j2]});
                    nr[i2][j2] = nr[i][j]+1;
                }
            }
        }
        Q.pop();
    }
    out << fin[x2][y2];
}