棋盘问题

Question

有一个尺寸为n * n的棋盘。该板上有 2 个方 block S(x1,y1) ;M(x2,y2)。 S 是一个固定点。 M 可以对角移动。它可以在 1 次移动中移动任意步数或跳跃。求 M 到达 S

所需的最小移动次数

我的方法:我们可以只计算对角线 block ，但我对跳跃感到困惑。谁能解释一下跳跃是什么意思？

Answer 1

我认为这里的跳跃是指棋子可以对角移动超过1步的情况。例如，如果位于 (1,1)，则可以一步转到 (3,3)。

假设上述情况，我编写了一个回溯算法。 这里的基本思想是获取所有可能的移动以到达目的地 (x,y) 坐标。它检查给定位置的所有有效移动并打印到达此处的路径。 construct_candidates() 将为您提供当前位置的所有有效候选坐标。它检查边界并验证我们之前没有访问过该棋 block ，如果满足这些条件，那么它就是该移动的有效候选者。

您可以轻松修改它以跟踪所遵循的最短路径。

#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)