#include #include #include #include #include #include #include struct coor { int x; int y; }; struct info{ struct coor prev_pos; bool already; int length; }; void min_mov_rec(int a, int b, struct info **tab, struct coor pos, int n); bool update(struct info **tab, struct coor pos, struct coor new_pos); bool update(struct info **tab, struct coor pos, struct coor new_pos) { struct info *info = &tab[pos.x][pos.y]; struct info *new_info = &tab[new_pos.x][new_pos.y]; if(! new_info->already) { // new_info->already = true; new_info->length = info->length + 1; new_info->prev_pos = pos; return true; } else { if(info->length + 1 < new_info->length) { new_info->length = info->length + 1; new_info->prev_pos = pos; return true; } } return false; } void min_mov_rec(int a, int b, struct info **tab, struct coor pos, int n) { int x = pos.x; int y = pos.y; if(x == n-1 && y == n-1) { // fprintf(stderr, "BINGO x y %d %d \n", a, b); return; } tab[x][y].already = true; // fprintf(stderr, "x y %d %d \n", x, y); for(int i = x-a ; i <= x+a ; i+=a) { for(int j = y-b ; j <= y+b ; j+=b) { if(i < 0 || j <0 || i >= n || j >= n) { ; } else if (x != i && y != j) { struct coor new_pos1; new_pos1.x = i; new_pos1.y = j; struct coor new_pos2; new_pos2.y = i; new_pos2.x = j; if(update(tab, pos, new_pos1)) min_mov_rec(a, b, tab, new_pos1, n); if (update(tab, pos, new_pos2)) min_mov_rec(a, b, tab, new_pos2, n); } } } } int min_mov(int a, int b, int n) { struct info **tab; struct coor pos; pos.x = 0; pos.y = 0; tab = malloc(sizeof(struct info*)*n); for(int i = 0 ; i < n ; i++) { tab[i] = malloc(sizeof(struct info)*n); for(int j = 0 ; j < n ; j++) { struct info info; info.already = false; info.length = -1; } } tab[0][0].length = 0; min_mov_rec(a, b, tab, pos, n); /* for(int i = 0 ; i < n ; i++) { for(int j = 0; j < n; j++) { fprintf(stderr, "(%d) ", tab[i][j].length); } fprintf(stderr,"\n"); } fprintf(stderr,"\n");*/ return tab[n-1][n-1].length; } int main(){ int n; scanf("%d",&n); // your code goes here for(int i = 1; i < n; i++) { for(int j = 1; j < n; j++) { int m = min_mov(j, i, n); if(m==0) m=-1; fprintf(stdout, "%d ", m); } printf("\n"); } return 0; }