论坛 › 数据结构与算法 › 马踏棋盘 算法 自己总结自己理解如有不对请指点，总感觉差点

奥普瓯江 发表于 2020-12-18 17:46:10

马踏棋盘 算法 自己总结自己理解如有不对请指点，总感觉差点

本帖最后由 奥普瓯江 于 2020-12-18 17:54 编辑

时间库我占时没用



#include <stdio.h>
#include <time.h>

#define X 6   //建立网格数量
#define Y 6

int chess;        //建立棋盘

int Function_Chess(int x, int y, int step);        //马踏棋盘程序
int Every_Chess(int *x1, int *y1, int count);        //每一步运行的程序count选项
void Print_Chess();                                        //打印棋盘

void Print_Chess()
{
        int i, j;
        for (i = 0; i < X; i++)
        {
                for (j = 0; j < Y; j++)
                {
                        printf("%3d", chess);
                }
                putchar('\n');
        }

}


int Every_Chess(int *x1, int *y1, int count)//因为要更x1与y1中的数值所以用指针
{
        switch (count)
        {
        case 0:        //上左
                {
                        if (*x1-1 >= 0 && *y1-2 >= 0 && chess[*x1-1][*y1-2] == 0)
                        {
                                *x1 -= 1;
                                *y1 -= 2;
                                return 1;
                        }       
                }
                break;
        case 1:        //上右
                {
                        if (*x1+1 <= X-1 && *y1-2 >= 0 && chess[*x1+1][*y1-2] == 0)
                        {
                                *x1 += 1;
                                *y1 -= 2;
                                return 1;
                        }       
                }
                break;
        case 2:        //右上
                {
                        if (*x1+2 <= X-1 && *y1-1 >= 0 && chess[*x1+2][*y1-1] == 0)
                        {
                                *x1 += 2;
                                *y1 -= 1;
                                return 1;
                        }       
                }
                break;
        case 3:        //右下
                {
                        if (*x1+2 <= X-1 && *y1+1 <= Y-1 && chess[*x1+2][*y1+1] == 0)
                        {
                                *x1 += 2;
                                *y1 += 1;
                                return 1;
                        }       
                }
                break;
        case 4:        //下右
                {
                        if (*x1+1 <= X-1 && *y1+2 <= Y-1 && chess[*x1+1][*y1+2] == 0)
                        {
                                *x1 += 1;
                                *y1 += 2;
                                return 1;
                        }       
                }
                break;
        case 5:        //下左
                {
                        if (*x1-1 >= 0 && *y1+2 <= Y-1 && chess[*x1-1][*y1+2] == 0)
                        {
                                *x1 -= 1;
                                *y1 += 2;
                                return 1;
                        }       
                }
                break;
        case 6:        //左下
                {
                        if (*x1-2 >= 0 && *y1+1 <= Y-1 && chess[*x1-2][*y1+1] == 0)
                        {
                                *x1 -= 2;
                                *y1 += 1;
                                return 1;
                        }       
                }
                break;
        case 7:        //左上
                {
                        if (*x1-2 >= 0 && *y1-1 >= 0 && chess[*x1-2][*y1-1] == 0)
                        {
                                *x1 -= 2;
                                *y1 -= 1;
                                return 1;
                        }       
                }
                break;
        default:
                break;
        }
        return 0;
}


int Function_Chess(int x, int y, int step)       
{
        int x1 = x, y1 = y;                        //临时变量
        int flag = 0, count = 0;        //flag 返回值的存储，count选项的存储
       
        chess = step;                        //把step中的数值传给棋盘
        if (step == X*Y)                        //打印棋盘中的数据
        {
                Print_Chess();
                return 1;
        }
        //再此段中下面这句话可以不需要，经过测试不会对结果产生影响
        //flag = Every_Chess(&x1, &y1, count);        //首次运行Every函数判断第一步是否可行选项值为0，因为要更改x1和y1的值所以用地址输入
        while (flag == 0 && count < 8)
        {
                //count++;
                flag = Every_Chess(&x1, &y1, count);        //如果第一步运行失败返回0就对另外七个方向进行判断
                count++;
        }

        while (flag)                //如果flag返回来的是1则运行西面的程序
        {
                if (Function_Chess(x1, y1, step+1))                //此处为递归，递归在归来的时候不是直接跳转到本函数结尾而是继续往下走一直往下执行，在本函数中flag等于0是递归返回得其中一个条件但是他不是立刻返回而是先执行if(flag == 0)然后一直到到“}” 在进行返回
                {
                        return 1;
                }

                x1 = x;
                y1 = y;
                count++; //这个是保证不能再原有基础上再次进行，运算而是对剩余部分进行运算，比如递归时进入站中的时1当他被归运算时及加一进行像下一个项进行运算

                flag = Every_Chess(&x1, &y1, count);        //此处如果不添加将在返回时没有办法从新计算因为返回时自带的count值有可能为1或者更大递归返回是整体储存
                while (flag == 0 && count < 8)
                {
                        //count++;
                        flag = Every_Chess(&x1, &y1, count);        //如果第一步运行失败返回0就对另外七个方向进行判断
                        count++;
                }

        }
        if (flag == 0)                //如果失败及x与y标志位的数值还原为0
        {
                chess = 0;
        }
        return 0;        //如果不加这条再Visual中他自动返回0也是可以的这是个结束语，如果想执行if(Function_chess)的return 1；就必须执行该程序

}
int main()
{
        int i, j;
        for (i = 0; i < X; i++)        //初始化棋盘
        {
                for (j = 0; j < Y; j++)
                {
                        chess = 0;
                }
        }


        //运行马踏棋盘程序
        if(!Function_Chess(6-1, 6-1, 0))//如果fuchtion函数运行结束后返回来的数值是0则打印print如果返回来的数值是1则结束程序，因为if内包含一个叹号取相反的意思
        {
                printf("马踏棋盘失败了！");
        }

       
        return 0;
}

查看完整版本: 马踏棋盘 算法 自己总结自己理解如有不对请指点，总感觉差点