马踏棋盘C语言实现（非递归、贪心）

第一次发文章，理解不了网上的另一种贪心非递归的代码，自己写了另一种实现方式，运行速度还可以，用ways_out的数组存放之前走错的方向，关于贪心，这里的解释是选择后面仍然有路且在8个方向中路径最少的一个方向，就理解成这里不走以后就没机会了吧

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define STACKINCREMENT 10
#define STACK_INIT_SIZE 64 

typedef struct step
{
    /* data */
    int x_pos;
    int y_pos;
    int dir;
    int ways_out[8];    //这条路是否走过但失败了，防止一直卡在一个方向上 ，1为走过且失败 
}step, *Step;

typedef step ElemType;
typedef struct 
{
    /* data */
    ElemType *top;
    ElemType *base;
    int stackSize; 
}sqStack;

void push(sqStack *s, ElemType e){
    if(s->top - s->base >= s->stackSize){
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT)*sizeof(ElemType));
        if(!s->base)
            exit(0);
        s->top = s->base + s->stackSize;
        s->stackSize = s->stackSize + STACKINCREMENT;
    }

    *(s->top) = e;
    s->top++;
}

void pop(sqStack *s, ElemType *e){
    if( s->top == s->base)
    return;
    *e = *--(s->top);
}

void InitStack(sqStack *s){
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!s->base)
    {
        exit(0);
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
//c1储存横坐标的变化，c2储存纵坐标的变化 
int c1[8] = {-2,-2, 2, 2, 1, 1,-1,-1};
int c2[8] = {-1, 1, 1,-1,-2, 2, 2,-2};
//棋盘 
int chessboard[8][8] = {0};
//找到正确的方向
int choice_num(Step s, int n);
int rightway(Step s){
    int i;
    step t = {0};
    int d[8] = {0,0,0,0,0,0,0,0};
    for(i=0; i<8; i++){
        if(s->x_pos + c1[i] >= 0 && s->x_pos + c1[i] < 8 && s->y_pos + c2[i] >= 0 && s->y_pos + c2[i] < 8 && !(s->ways_out[i]) && !chessboard[s->x_pos+c1[i]][s->y_pos+c2[i]]){
            t.x_pos = s->x_pos + c1[i];
            t.y_pos = s->y_pos + c2[i];
            //计算这个方向上可以有多少种选择
            d[i] += choice_num(&t,i);
        }
    }
    int min = 9;
    int choice = 0;
    for(i=0; i<8; i++){          //贪心，找出最少可能性的方向
        if(d[i]<min && d[i]){
            min = d[i];
            choice = i;
        }
    }
    if(min == 9){
        //八方走不通
        return 0;
    }else{
        //找到了
        s->dir = choice;
        return 1;
    }
}

//判断下一步的下一步有多少种可能
int choice_num(Step s, int n){
    int i;
    int count = 0;
    step ss = {s->x_pos, s->y_pos, -1};
    if(ss.x_pos >= 0 && ss.x_pos < 8 && ss.y_pos >= 0 && ss.y_pos < 8){
        for(i=0; i<8; i++){
            if(ss.x_pos + c1[i] >= 0 && ss.x_pos + c1[i] < 8 && ss.y_pos + c2[i] >= 0 && ss.y_pos + c2[i] < 8 ){
                  count++;         
            }
        }
    }
    return count;
}

void DFS(int x, int y){
    step s = {x, y, -1, {0}};
    chessboard[x][y] = 1;
    int i = 0;
    int j = 0;
    int counts = 1;
    sqStack stack;
    InitStack(&stack);
    //判断下一步该往哪走
    do{
        if(rightway(&s)){
            push(&stack, s);
    //上一步压栈，更新下一步
            s.x_pos += c1[s.dir];
            s.y_pos += c2[s.dir];
            s.dir = 0;
            for(i=0; i<8; i++){
                if(!s.ways_out[i])
                s.ways_out[i] = 0;
            }
            chessboard[s.x_pos][s.y_pos] = ++counts;

        }else{
            chessboard[s.x_pos][s.y_pos] = 0;
    //取出上一步，做标记
            pop(&stack, &s);
            s.ways_out[s.dir] = 1;  //这个方向无需再尝试
            counts--;
        }
    }while(counts < 64 && stack.base != stack.top );
    if(counts == 64){
    for(i = 0; i < 8; i++){
        for(j = 0; j < 8; j++){
                printf("%2d ", chessboard[i][j]);
        }
        printf("\n");
    }
    }else{
        printf("失败");
    }
}

int main(){
    clock_t start,finish;
    start = clock();
    DFS(1,1);
    finish = clock();
    printf("耗时%f秒",(double)(finish - start)/CLOCKS_PER_SEC);
    return 0;
}

还是蛮快的？如能帮助到大家，不胜荣幸。有问题欢迎评论区留言。转载请注明出处