棋盘问题

Question

有一个尺寸为n * n的棋盘。您在该板上获得2个方格S(x1,y1); M(x2,y2)。 S是一个固定点。 M可以对角移动。它可以移动任意数量的步骤或跳跃。找到移动的最小数目M需要达到S

我的方法：我们算了算对角块，但我很困惑与跳跃。任何人都可以解释跳跃意味着什么吗？

Answer 1

我觉得这里的跳棋是指棋子可以对角移动超过1步的情况。例如，如果在（1,1）处，那么它可以在一步中转到（3,3）。

假设上述情况，我编写了一个bactracking算法。 这里的基本想法是让所有可能的动作到达目标（x，y）坐标。它会检查给定位置的所有有效移动并打印到达此处的路径。 construct_candidates()会为您提供当前位置的所有有效候选坐标。它会检查边界，并验证我们以前没有访问过国际象棋棋子，如果这些条件得到满足，那么它就是移动的有效候选者。

您可以轻松修改它以跟踪最短路径。

#define N 4 /* Chess Board Dimension */ 
#define TRUE  1 
#define FALSE 0 

#define START_X 0 
#define START_Y 0 
#define TARGET_X 1 
#define TARGET_Y 3 

typedef short int bool; 

typedef struct point_ { 
    int x; 
    int y; 
} point_t; 


bool is_candidate_valid (point_t *a, int k, int new_x, int new_y) 
{ 
    int i; 
    /* Check bounds */ 
    if ((new_x < 0) || (new_x > (N-1)) || 
     (new_y < 0) || (new_y > (N-1))) { 
     return FALSE; 
    } 

    /* Check if this new position is already in the path followed */ 

    for (i = 0; i < k; i++) { 
     if (a[i].x == new_x && a[i].y == new_y) { 
      return FALSE; 
     } 
    } 
    return TRUE; 
} 

void construct_candidates (point_t *a, int k, point_t *candidates, int *n_candidates) 
{ 
    int delta; 
    *n_candidates = 0; 
    int new_x, new_y; 

    for (delta = 1; delta <= (N-1); delta++) { 

     new_x = a[k-1].x + delta; 
     new_y = a[k-1].y + delta; 

     if (is_candidate_valid (a, k, new_x, new_y) == TRUE) { 
      candidates[*n_candidates].x = new_x; 
      candidates[*n_candidates].y = new_y; 
      (*n_candidates)++; 
     } 

     new_x = a[k-1].x + delta; 
     new_y = a[k-1].y - delta; 

     if (is_candidate_valid (a, k, new_x, new_y) == TRUE) { 
      candidates[*n_candidates].x = new_x; 
      candidates[*n_candidates].y = new_y; 
      (*n_candidates)++; 
     } 

     new_x = a[k-1].x - delta; 
     new_y = a[k-1].y + delta; 

     if (is_candidate_valid (a, k, new_x, new_y) == TRUE) { 
      candidates[*n_candidates].x = new_x; 
      candidates[*n_candidates].y = new_y; 
      (*n_candidates)++; 
     } 

     new_x = a[k-1].x - delta; 
     new_y = a[k-1].y - delta; 

     if (is_candidate_valid (a, k, new_x, new_y) == TRUE) { 
      candidates[*n_candidates].x = new_x; 
      candidates[*n_candidates].y = new_y; 
      (*n_candidates)++; 
     } 
    } 
} 

bool is_a_solution (point_t *a, int k) 
{ 
    if (a[k-1].x == TARGET_X && a[k-1].y == TARGET_Y) { 
     return TRUE; /* Actual Solution found */ 
    } 
    if (k == (N*N)) { 
     return TRUE; /* No Solution found */ 
    } 
    return FALSE; 
} 

void process_solution (point_t *a, int k) 
{ 
    int i; 

    if (k == (N*N)) { 
     return; /* No solution Possible */ 
    } 

    for (i = 0; i < k; i++) { 
     printf ("(%d, %d) ", a[i].x, a[i].y); 
    } 
    printf ("\n"); 
} 


void backtrack (point_t *a, int k) 
{ 
    int i, n_candidates; 
    point_t candidates[4*(N-1)]; 

    if (is_a_solution (a, k) == TRUE) { 
     process_solution (a, k); 
     return; 
    } 

    construct_candidates (a, k, candidates, &n_candidates); 
    for (i = 0; i < n_candidates; i++) { 
     a[k].x = candidates[i].x; 
     a[k].y = candidates[i].y; 

     backtrack (a, k + 1); 
    } 
} 

int main() 
{ 
    point_t a[N*N]; 
    /* Fill up the initial position */ 
    a[0].x = START_X; 
    a[0].y = START_Y; 

    backtrack (a, 1); 
} 

Output: 

(0, 0) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (1, 1) (2, 2) (3, 1) (1, 3) 
(0, 0) (1, 1) (2, 2) (1, 3) 
(0, 0) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3) 
(0, 0) (1, 1) (2, 0) (3, 1) (1, 3) 
(0, 0) (1, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (1, 1) (0, 2) (1, 3) 
(0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3) 
(0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) 
(0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (1, 3) 
(0, 0) (1, 1) (3, 3) (2, 2) (1, 3) 
(0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3) 
(0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (1, 3) 
(0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) 
(0, 0) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3) 
(0, 0) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (2, 2) (3, 1) (1, 3) 
(0, 0) (2, 2) (1, 3) 
(0, 0) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3) 
(0, 0) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (2, 2) (1, 1) (0, 2) (1, 3) 
(0, 0) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) 
(0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3) 
(0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (3, 3) (2, 2) (3, 1) (1, 3) 
(0, 0) (3, 3) (2, 2) (1, 3) 
(0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3) 
(0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (1, 3) 
(0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3) 
(0, 0) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (0, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3) 
(0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)