美文网首页
马踏棋盘 (对应于小甲鱼视频的代码)

马踏棋盘 (对应于小甲鱼视频的代码)

作者: 行走小样 | 来源:发表于2019-02-28 21:08 被阅读0次

#include<stdio.h>

#include<time.h>

#define X 8

#define Y 8

int chess[X][Y];

int c = 1;

//找到基于(x,y)位置的下一个可走位置

int nextxy(int *x, int *y, int count)

{

switch (count)

{

case 0:

if (*x + 2 <= X - 1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)

{

*x += 2;

*y -= 1;

return 1;

}

break;

case 1:

if (*x + 2 <= X - 1 && *y + 1 <= Y - 1 && chess[*x + 2][*y + 1] == 0)

{

*x += 2;

*y += 1;

return 1;

}

break;

case 2:

if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)

{

*x -= 2;

*y -= 1;

return 1;

}

break;

case 3:

if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0)

{

*x -= 2;

*y += 1;

return 1;

}

break;

case 4:

if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)

{

*x += 1;

*y -= 2;

return 1;

}

break;

case 5:

if (*x + 1 <= X - 1 && *y + 2 <= Y - 1 && chess[*x + 1][*y + 2] == 0)

{

*x += 1;

*y += 2;

return 1;

}

break;

case 6:

if (*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)

{

*x -= 1;

*y -= 2;

return 1;

}

break;

case 7:

if (*x - 1 >= 0 && *y + 2 <= Y - 1 && chess[*x - 1][*y + 2] == 0)

{

*x -= 1;

*y += 2;

return 1;

}

break;

default:

break;

}

return 0;

}

void print()

{

int i, j;

for (i = 0; i < X; i++)

{

for (j = 0; j < Y; j++)

{

printf("%2d\t", chess[i][j]);

}

printf("\n");

}

printf("\n");

}

//深度优先遍历棋盘 (x,y)为起始位置坐标,tag为标记变量,每走一步,tag加一

int Travalchesboard(int x, int y, int tag)

{

int x1 = x, y1 = y, flag = 0, count = 0;

chess[x][y] = tag;

if (tag == X * Y)

{

//打印棋盘

print();

return 1;

}

flag = nextxy(&x1, &y1, count);              //打印马的下一个坐标(x1,y1),如果找到flag=1,否则=0;

while (flag == 0 && count < 7)

{

count++;

flag = nextxy(&x1, &y1, count);

}

while (flag)

{

if (Travalchesboard(x1, y1, tag + 1))    //这里这个递推需要好好理解一下,在不满足条件出去一个函数后,tag会减一,从而实现不对则往回返

{

return 1;

}

x1 = x;

y1 = y;

count++;

flag = nextxy(&x1, &y1, count); //出现意外,继续找下一步可走坐标

}

if (flag == 0)

{

chess[x][y] = 0;

}

return 0;

}

int main()

{

int i, j;

clock_t start, finish;

start = clock();

for (i = 0; i < X; i++)

{

for (j = 0; j < Y; j++)

{

chess[i][j] = 0;

}

}

if (!Travalchesboard(2, 0, 1))

{

printf("sorry,fault!! \n");

}

finish = clock();

printf("\n time: \n", (double)(finish - start) / CLOCKS_PER_SEC);

return 0;

}

相关文章

  • 马踏棋盘 (对应于小甲鱼视频的代码)

    #include #include #define X 8 #define Y 8 int chess[X][Y]...

  • 马踏棋盘java实现 详解注释

    最近对算法方面有点兴趣马踏棋盘有用到贪心算法 回溯算法 回溯是当前棋盘状态 54时下一步已经没地方了 马儿踏完整...

  • 马踏棋盘算法2018-06-09

    /June 8,2018 Author GH //该代码用递归实现了马踏棋盘算法//反思,在实现过程中滥用全局变量...

  • 马踏棋盘算法

    最近在学习深度优先搜索算法,接触到了马踏棋盘,决定尝试一下。 涉及算法:递归,回溯法,深度优先搜索算法 题目需求:...

  • 马踏棋盘算法

    由于今天的马踏棋盘算法并不是使用OC编写,所以,今天的标题也就不是"使用OC....."了,下面直接开始我们的正题...

  • 马踏棋盘算法

    问题定义: 将马随机放在国际象棋的Board[0~7][0~7]的某个方格中,马按走棋规则进行移动。,走遍棋盘上全...

  • 马踏棋盘(结合贪心)

    将能选择的点进行递归,不通就回溯 结合贪心算法优化将可跳转的点的下一步进行非递减排序,这样可以尽量少的回溯

  • 自学Python:马踏棋盘

    国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。 要求每个...

  • 学习网站和不错工具

    C、C++、单片机等学习:小甲鱼论坛小甲鱼老师目前所有视频教程下载地址小甲鱼的《零基础入门学习C语言》小甲鱼的《零...

  • 马踏棋盘(贪心算法)

    需求 将马随机放在国际象棋的Board[0~7][0~7]的某个方格中,马按走棋规则进行移动。,走遍棋盘上全部64...

网友评论

      本文标题:马踏棋盘 (对应于小甲鱼视频的代码)

      本文链接:https://www.haomeiwen.com/subject/abqluqtx.html