Cod sursa(job #2114908)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 26 ianuarie 2018 07:58:51
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream f("kdrum.in");
ofstream g("kdrum.out");

struct triplet{
    int x,y,nd;
};

int nr = 0;
int n,m,k;
int div[52][52];
int drum[52][52][100];

int x1,y1,x2,y2;
int  fv[12005];
int inv[12005];

queue <triplet> q;

int cmmdc(int a, int b){

    int c;
    while(b>0){

        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

int lee(){

    q.push({x1,y1,1});
    drum[x1][y1][1] = 1;
    /*g<<nr<<"\n";
    for(int i =1 ;i<= nr; i++)
    {
        g<<inv[i]<<" ";
    }
    g<<"\n";
    */
    while(!q.empty()){

        triplet t = q.front();
        triplet ts;
        q.pop();

        for(int i =0; i< 4; i++)
        {
            ts.x  = t.x  + dx[i];
            ts.y  = t.y  + dy[i];

            if(div[ts.x][ts.y]!=0){

                int dv = inv[t.nd];
                ts.nd = fv[dv*cmmdc(k/dv,div[ts.x][ts.y])];

                if(drum[ts.x][ts.y][ts.nd] ==0){

                    drum[ts.x][ts.y][ts.nd] = drum[t.x][t.y][t.nd] + 1;
                    q.push(ts);
                    //g<<ts.x<<" "<<ts.y<<" "<<inv[ts.nd]<<" "<<drum[ts.x][ts.y][ts.nd]<<"\n";
                    if(ts.x == x2 && ts.y == y2 && ts.nd == nr)
                    {
                        return drum[ts.x][ts.y][ts.nd];
                    }
                }
            }

        }

    }
    return 0;


}

int main(){

    f>>n>>m>>k;
    f>>x1>>y1>>x2>>y2;

    nr = 0;
    for(int i =1; i<=k;i++){

        if(k%i==0)
        {
            nr++;
            fv[i]=nr;
            inv[nr]=i;
        }
    }

    for(int i =1; i<= n; i++){

        for(int j=1; j<= m; j++){

            f>>div[i][j];
        }
    }
    g<<lee();
    f.close();
    g.close();
    return 0;
}