骑士的堆栈旅行问题。 （输出无法正常工作。）

问题描述 投票：0回答：1

这是一道用堆栈展示棋子马的移动路径的问题。在国际象棋中，马的走法是L形。棋盘的坐标水平用a到b表示，垂直用8比1表示。如果我输入起始位置和到达位置，程序应该运行，以便骑士显示已经通过的坐标。

但是与我的预期相反，骑士经过的路径没有正确输出。如果我输入b7作为起点，e2作为终点，应该输出如下：

b7 c2 e6 g7 h5 g3 e2

但是打印出来是这样的：

b7 e2
---
3
e2

我不知道这是怎么回事。如果您能更正代码，我将非常感激。

接下来是我编写的代码。 （希望大家不要修改gstack.c和gstack.h文件中的代码。）

typedef 
    struct {
        void * buffer ;
        int unit ;
        int capacity ;
        int size ;
    } 
    gstack_t ;

gstack_t * 
create_stack (int capacity, int unit) ;

void
delete_stack (gstack_t * stack) ;

int 
push (gstack_t * stack, void * elem) ;

int
pop (gstack_t * stack, void * elem) ;

int 
is_empty (gstack_t * stack) ;

int 
is_full (gstack_t * stack) ;

int
get_size (gstack_t * stack) ;

int
get_element (gstack_t * stack, int index, void * elem) ;

gstack.c

#include <stdlib.h>
#include <string.h>
#include "gstack.h"

gstack_t * 
create_stack (int capacity, int unit) 
{
    gstack_t * st = malloc(sizeof(gstack_t)) ;
    st->capacity = capacity ;
    st->unit = unit ;
    st->size = 0 ;
    st->buffer = calloc(capacity, unit) ;
    return st ;
}

void
delete_stack (gstack_t * st) 
{
    if (st->buffer != 0x0)
        free(st->buffer) ;
    free(st) ;
}

int 
push (gstack_t * st, void * elem)
{
    if (is_full(st))
        return 0 ;
    // memcpy: memory + copy(메모리의 값 복사.)
    // void* memcpy(*(복사받을데), *(복사할데), size(바이트단위));
    memcpy(st->buffer + ((st->size) * (st->unit)), elem, st->unit) ;
    st->size += 1 ;
    return 1 ;
}

int
pop (gstack_t * st, void * elem)
{
    if (is_empty(st)) 
        return 0 ;

    memcpy(elem, st->buffer + (st->size - 1) * st->unit, st->unit) ;
    st->size -= 1 ;
    return 1 ;
}

int 
is_empty (gstack_t * st) 
{
    return (st->size == 0) ;
}

int 
is_full (gstack_t * st) 
{
    return (st->size == st->capacity) ;
}

int
get_size (gstack_t * st) 
{
    return st->size ;
}

int
get_element (gstack_t * st, int index, void * elem)
{
    if (st->size <= index)
        return 0 ;

    memcpy(elem, st->buffer + index * st->unit, st->unit) ;
    return 1 ;
}

骑士.c

#include <stdio.h>
#include <stdlib.h>
#include "gstack.h"

int visited[8][8] = {0,};

typedef 
    enum {
        // e.g U2R1: a kinght moves 2 squares Upward and 1 squares Right.
        U2R1, U2L1, L2U1, L2D1, D2L1, D2R1, R2D1, R2U1
    } 
    dir;

char departure_h;
int departure_v;
char arrival_h;
int arrival_v;

void depart_to_arrival() {
    scanf(" %c %d", &departure_h, &departure_v);   // input departure coordinate 
    scanf(" %c %d", &arrival_h, &arrival_v);       // input arrival coordinate;
    printf("---\n");
}

void search() {
    gstack_t * hs = create_stack(64, sizeof(char)); // about horizontal coordinate (X, char a~b)
    gstack_t * vs = create_stack(64, sizeof(int));  // about vertical coordinate (Y, integer 8~1)
    gstack_t * ds = create_stack(64, sizeof(dir));  // about diretion ( U2R1, U2L1, ... R2U1)

    int found = 0; // 목적지에 도달했는지를 나타냄.

    char h = departure_h;   // horizon(x)
    int v = departure_v;    // vertical(y) 
    dir d = U2R1;           // direction

    visited[v-1][h-'a'] = 1;

    push(hs, &h); 
    push(vs, &v);
    push(ds, &d);

    while(is_empty(hs) == 0 && !found) {
        pop(hs, &h); pop(vs, &v); pop(ds, &d);

        if(h == arrival_h && v == arrival_v) {  // check arrivial
            found = 1;
            push(hs, &h); push(vs, &v); 
            break;  // end of search
        }

        for(dir i=d; i<=R2U1; i++) {  
            char nh=h;
            int nv=v;
            switch(i) {
                case U2R1: {
                    nh = h+1;
                    nv = v+2;
                    break ;
                }
                case U2L1: {
                    nh = h-1;
                    nv = v+2;
                    break ;
                }
                case L2U1: {
                    nh = h-2;
                    nv = v+1;
                    break ;
                } 
                case L2D1: {
                    nh = h-2;
                    nv = v-1;
                    break ;
                } 
                case D2L1: {
                    nh = h-1;
                    nv = v-2;
                    break ;
                }
                case D2R1: {
                    nh = h+1;
                    nv = v-2;
                    break ;
                }
                case R2D1: {
                    nh = h+2;
                    nv = v-1;
                    break ;
                }
                case R2U1: {
                    nh = h+2;
                    nv = v+1;
                    d = U2R1;
                    break ;
                }
                default: {
                    continue;
                }
            }

            if ('a'<=nh && nh <='h' && 1<=nv && nv <=8 && !visited[nv-1][nh-'a']) {      
                visited[nv-1][nh-'a']=1;
                push(hs, &nh); push(vs, &nv);  
                push(ds, &i);       
                break;
            }
        }
    }

    if(found) {
        for(int i=get_size(hs); i>=0; i--) {
            char h;
            int v;
            get_element(hs, i, &h); get_element(vs, i, &v);
            printf("%c%d\n", h, v);
        }
    }
    else {
        printf("failed.\n");
    }
}

int main(void) {
    depart_to_arrival();
    search();

    return EXIT_SUCCESS;
}

我在搜索函数中的while语句中删除了(L 43) pop()，并修改了代码，将if语句(L 101)的else语句修改为如果不满足条件则弹出，即如果关闭则弹出棋盘。但它不能正常工作。我知道推送不能正常工作，但我真的不知道……编码高手，请救救我。请。

c data-structures stack
1个回答
0
投票

主要问题是你的算法逻辑：堆栈永远不会有多个元素。每个堆栈都以一个元素开始，然后主循环开始：在主循环的每次迭代中，您从每个堆栈中弹出一项，并在每个堆栈上推送一项。因此，这些堆栈不可能获得超过一件物品。

我不清楚您打算实现哪种算法，但由于 8x8 板只有 64 个方格，我会在没有堆栈的情况下执行此操作。相反，使用 

visited
数组不仅可以指示是否访问过某个方格，还可以指示到达该方格的步数。您可以从给定的方块开始，然后应用骑士跳跃来找到具有下一个距离的方块。由于现在您尚未将这些结果存储在堆栈中，因此您将扫描 
visited
数组以再次找到这些结果，并通过另一次移动来扩展它们，...等等。

为了打印路径，您将沿着路径向后移动，始终寻找会缩短距离的移动。由于这会向后打印路径，因此从头到尾执行第一阶段会很有帮助。

这确实是一种广度优先搜索，其中通过扫描棋盘来替换队列。但它保证你找到最短路径。

不是必需的，但在一维 (0..63) 而不是二维 ('a'..'h', 1..8) 中工作可能更容易。

这是一个实现：

#include <stdio.h>
#include <stdlib.h>

int pair_to_square(char h, int v) {
    return (h - 'a') + 8 * (v - 1);
}

void depart_to_arrival(int * departure, int * arrival) {
    // Avoid globals
    char departure_h;
    int departure_v;
    char arrival_h;
    int arrival_v;

    scanf(" %c %d", &departure_h, &departure_v);   // input departure coordinate 
    scanf(" %c %d", &arrival_h, &arrival_v);       // input arrival coordinate;
    printf("---\n");
    *departure = pair_to_square(departure_h, departure_v);
    *arrival   = pair_to_square(arrival_h, arrival_v);
}

int apply_jump(int square, int i) {
    static int jumps[8] = {-17, -15, -10, -6, 6, 10, 15, 17}; 
    int newsquare = square + jumps[i];
    int coldiff = abs(square % 8 - newsquare % 8);
    if (newsquare >= 64 || coldiff > 2) return -1;
    return newsquare;
}

void search(int departure, int arrival) {
    int visited[64] = {0,};
    visited[arrival] = 1; // Start from the end
    int distance = 1;
    while (!visited[departure]) {
        // Scan the board to find the squares with the current distance
        for (int square = 0; square < 64; square++) {
            if (visited[square] != distance) continue;
            for (int i = 0; i < 8; i++) {
                int newsquare = apply_jump(square, i);
                if (newsquare >= 0 && !visited[newsquare]) {
                    // Mark the distance at the target of the played move
                    visited[newsquare] = distance + 1;
                }
            }
        }
        distance++;
    }
    // Traverse the path in opposite direction, and print it
    while (distance-- > 0) {
        printf("%c%d\n", 'a' + (departure % 8), (departure / 8) + 1);
        for (int i = 0; i < 8; i++) {
            int newsquare = apply_jump(departure, i);
            if (newsquare >= 0 && visited[newsquare] == distance) {
                departure = newsquare;
                break;
            }
        }
    }
}

int main(void) {
    int departure, arrival;
    depart_to_arrival(&departure, &arrival);
    search(departure, arrival);
    return EXIT_SUCCESS;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.