美文网首页
马的遍历问题(打印访问象棋棋盘所有位置需要的步数)

马的遍历问题(打印访问象棋棋盘所有位置需要的步数)

作者: 疋瓞 | 来源:发表于2022-01-02 21:29 被阅读0次

1、环境配置:

  • 系统:win10
  • 编程语言:C
  • 编译器:DevC++

2、算法思想:

马的遍历问题,就是希望在一个规定大小的棋盘(M*N)上面,马从第(x,y)点出发,一直遍历所有的点,打印出访问某一个点所需要的步数。按照规则马能够跳跃的方向有8种可能(如下图所示):


马的遍历.png

3、代码:

#include <stdio.h>

void F_1(int a[10][9],int i,int j,int r,int l,int n); //r为二维数组行数,l为二维数组列数,n为访问次数,默认传1 

int main(){
    int A[10][9];
    int B[3][3];
    //二维数组初始化 
    for(int i=0;i<10;i++){
        for(int j=0;j<9;j++){
            A[i][j]=-1;
        }
    }
    //打印二维数组
    for(int i=0;i<10;i++){
        for(int j=0;j<9;j++){
            printf("%d ",A[i][j]); 
        }
        printf("\n");
    } 
    
    F_1(A,0,7,10,9,1);
    
    printf("\n");
    //打印二维数组
    for(int i=0;i<10;i++){
        for(int j=0;j<9;j++){
            if(A[i][j]!=-1)
            {
                printf(" %d ",A[i][j]); 
            }
            else{
                printf("%d ",A[i][j]); 
            }
        }
        printf("\n");
    } 
    
    return 0;
}


//遍历棋盘函数F_1 
void F_1(int a[10][9],int i,int j,int r,int l,int n)
{
    //起始点初始化
    if(n==1){
        a[i][j]=0;
    } 
    //先访问1点
    if(((i-2>-1)&&(i-2<r))&&((j+1>-1)&&(j+1<l))){
        if((a[i-2][j+1]==-1)||(n<a[i-2][j+1])){
            a[i-2][j+1]=n;
            F_1(a,i-2,j+1,r,l,n+1);
        }
    }
    //再访问2点
    if(((i-1>-1)&&(i-1<r))&&((j+2>-1)&&(j+2<l))){
        if((a[i-1][j+2] == -1)||(n<a[i-1][j+2])){
            a[i-1][j+2]=n;
            F_1(a,i-1,j+2,r,l,n+1); 
        }
    }
    //再访问3点
    if(((i+1>-1)&&(i+1<r))&&((j+2>-1)&&(j+2<l))){
        if((a[i+1][j+2] == -1)||(n<a[i+1][j+2])){
            a[i+1][j+2]=n;
            F_1(a,i+1,j+2,r,l,n+1); 
        }
    }
    //再访问4点
    if(((i+2>-1)&&(i+2<r))&&((j+1>-1)&&(j+1<l))){
        if((a[i+2][j+1] == -1)||(n<a[i+2][j+1])){
            a[i+2][j+1]=n;
            F_1(a,i+2,j+1,r,l,n+1); 
        }
    }
    //再访问5点
    if(((i+2>-1)&&(i+2<r))&&((j-1>-1)&&(j-1<l))){
        if((a[i+2][j-1] == -1)||(n<a[i+2][j-1])){
            a[i+2][j-1]=n;
            F_1(a,i+2,j-1,r,l,n+1); 
        }
    }
    //再访问6点
    if(((i+1>-1)&&(i+1<r))&&((j-2>-1)&&(j-2<l))){
        if((a[i+1][j-2] == -1)||(n<a[i+1][j-2])){
            a[i+1][j-2]=n;
            F_1(a,i+1,j-2,r,l,n+1); 
        }
    }
    //再访问7点
    if(((i-1>-1)&&(i-1<r))&&((j-2>-1)&&(j-2<l))){
        if((a[i-1][j-2] == -1)||(n<a[i-1][j-2])){
            a[i-1][j-2]=n;
            F_1(a,i-1,j-2,r,l,n+1); 
        }
    }
    //再访问8点
    if(((i-2>-1)&&(i-2<r))&&((j-1>-1)&&(j-1<l))){
        if((a[i-2][j-1] == -1)||(n<a[i-2][j-1])){
            a[i-2][j-1]=n;
            F_1(a,i-2,j-1,r,l,n+1); 
        }
    }
        
}

4、结果展示:

结果1.png 结果2.png

5、反思总结:

  • 伪代码如下:
void init(a[m][n])//将a[m][n]初始化为值全部为“-1”的二维数组 
void F(int a[m][n],int i,int j,int r,int l,int n)////r为二维数组行数,l为二维数组列数,n为访问次数,默认传1 。
{
    //起始位置初始为0
    if(n==1) then a[i][j]=0;
    //访问位置1 
    if(r>(i-2)>-1&&l>(j+1)>-1) then{
        if((a[i-2][j+1]==-1)||(n<a[i-2][j+1])) then{
            a[i-2][j+1]=n;
            F_1(a,i-2,j+1,n+1);
        }
    }
    //访问位置2 
    if(r>(i-1)>-1&&l>(j+2)>-1) then{
        if((a[i-1][j+2]==-1)||(n<a[i-1][j+2])) then{
            a[i-1][j+2]=n;
            F_1(a,i-1,j+2,n+1);
        }
    }
    //访问位置3 
    if(r>(i+1)>-1&&l>(j+2)>-1) then{
        ... 
    }
    //访问位置4 
    if(r>(i+2)>-1&&l>(j+1)>-1) then{
        ... 
    }
    //访问位置5 
    if(r>(i+2)>-1&&l>(j-1)>-1) then{
        ... 
    }
    //访问位置6 
    if(r>(i+1)>-1&&l>(j-2)>-1) then{
        ... 
    }
    //访问位置7 
    if(r>(i-1)>-1&&l>(j-2)>-1) then{
        ... 
    }
    //访问位置8
    if(r>(i-2)>-1&&l>(j-1)>-1) then{
        ... 
    } 
} 

相关文章

  • 马的遍历问题(打印访问象棋棋盘所有位置需要的步数)

    1、环境配置: 系统:win10 编程语言:C 编译器:DevC++ 2、算法思想: 马的遍历问题,就是希望在一个...

  • 象棋盘上的马

    窝心马、屏风马、拐子马…… 这种种的标签 很容易让人想到这是匹“病”马 马在槽枥中的嘶叫 才能听出它的雄心 但它一...

  • 二、二叉树

    前言 遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。 前序遍历:根节...

  • 7.4图的应用:骑士周游问题

    在一个国际象棋棋盘上,一个棋子“马” (骑士),按照“马走日”的规则,从一个格子出发,要走遍所有棋盘格恰好一次。把...

  • LeetCode之Print Binary Tree(Kotli

    问题: 方法:其实主要就是两步,第一步是通过深度优先遍历所有的节点,第二步是根据遍历的位置,遍历的层级判断在数组中...

  • 下棋

    儿子和侄子他们创造了一种新的象棋玩法,大致和军棋相似,把所有的棋子倒扣在棋盘上,只需占用棋盘的一半位置。 黑红自选...

  • 为什么杰出人物能够看到“一片森林”,而普通人,却只看见“一棵树”

    国际象棋大师来讲,对手每下出一步棋,只有短短几秒钟的时间来研究棋盘,因此,他们将准确地记住大多数棋子在棋盘上的位置...

  • 0037-八皇后问题

    问题描述 会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8...

  • 马踏棋盘算法

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

  • 自学Python:马踏棋盘

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

网友评论

      本文标题:马的遍历问题(打印访问象棋棋盘所有位置需要的步数)

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