Pagini recente » Cod sursa (job #1889581) | Cod sursa (job #1758933)
#include <cstdio>
#include <utility>
#include <algorithm>
#define mycreation std::pair <int, int>
#define x first
#define y second
#define NRDIR 4
int dl[NRDIR]={-1, 0, 1, 0};
int dc[NRDIR]={0, 1, 0, -1};
#define MAXN 50
#define MAXU 220
#define MAXK 12000
int e[MAXK+1], d[MAXU+1], t[(MAXN+3)*(MAXN+3)][MAXU+1];
int v[(MAXN+3)*(MAXN+3)], dist[(MAXN+3)*(MAXN+3)][MAXU+1];
mycreation q[(MAXN+3)*(MAXN+3)*MAXU+1];
inline int gcd(int a, int b){
int r;
while(b){
r=a%b;
a=b;
b=r;
}
return a;
}
int main(){
int nrlin, nrcol, k, a, b, l, c, i, j, p, u, st, dr, lim;
FILE *fin, *fout;
fin=fopen("kdrum.in", "r");
fout=fopen("kdrum.out", "w");
fscanf(fin, "%d%d%d%d%d%d%d", &nrlin, &nrcol, &k, &a, &b, &l, &c);
for(i=1; i<=nrlin; i++){
for(j=1; j<=nrcol; j++){
p=i*(nrcol+1)+j;
fscanf(fin, "%d", &v[p]);
if(v[p]) v[p]=gcd(v[p], k);
}
}
u=0;
for(i=1; i<=k; i++){
if(k%i==0){
d[++u]=i;
e[i]=u;
}
}
lim=(nrlin+1)*(nrcol+1);
for(i=1; i<=lim; i++)
if(v[i])
for(j=1; j<=u; j++)
t[i][j]=e[gcd(v[i]*d[j], k)];
st=0;
dr=1;
q[0].x=a*(nrcol+1)+b;
q[0].y=e[v[q[0].x]];
dist[q[0].x][q[0].y]=1;
while((q[st].x!=q[0].x)||(q[st].y!=u)){
for(i=0; i<NRDIR; i++){
p=q[st].x+(nrcol+1)*dl[i]+dc[i];
if((v[p])&&(!dist[p][t[p][q[st].y]])){
dist[p][t[p][q[st].y]]=dist[q[st].x][q[st].y]+1;
q[dr].x=p;
q[dr].y=t[p][q[st].y];
dr++;
}
}
st++;
}
fprintf(fout, "%d\n", dist[q[st].x][q[st].y]);
fclose(fin);
fclose(fout);
return 0;
}