Cod sursa(job #2600889)

Utilizator matei123Biciusca Matei matei123 Data 13 aprilie 2020 13:53:35
Problema Kdrum Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("kdrum.in"); ofstream g("kdrum.out");
int n, m, k, startx, starty, stopx, stopy, matrix[55][55], nr, a[12005], b[12005], dp[55][55][105];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct element
{   int x, y, c; };
queue <element> q;
void bfs_lee()
{   while (!q.empty())
    {   element t = q.front();
        if (t.x == stopx && t.y == stopy && t.c == nr)
        {   g << dp[t.x][t.y][t.c];
            return;
        }
        q.pop();
        for (int xx,yy,w = 0; w < 4; ++w)
        {   xx = t.x + dx[w]; yy = t.y + dy[w];
            if (!matrix[xx][yy]) continue;
            int cmmdc = a[t.c];
            int new_cmmdc = __gcd(cmmdc * matrix[xx][yy], k);
            if (dp[xx][yy][b[new_cmmdc]] != 0) continue;
            dp[xx][yy][b[new_cmmdc]] = 1 + dp[t.x][t.y][t.c];
            q.push({xx, yy, b[new_cmmdc]});
        }
    }

}
int main()
{   f >> n >> m >> k >> startx >> starty >> stopx >> stopy;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) f >> matrix[i][j];
    for (int i = 1; i <= k; ++i)
        if (k % i == 0)
        {   ++nr;
            a[nr] = i;
            b[i] = nr;
        }
    int cmmdc = __gcd(k, matrix[startx][starty]);
    q.push({startx, starty, b[cmmdc]});
    dp[startx][starty][b[cmmdc]] = 1;
    bfs_lee();
    g.close(); return 0;
}