C语言-数据结构-图的应用-马踏棋盘

今天药忘吃喽~ 2022-05-15 08:19 157阅读 0赞

/*
     马踏棋盘算法: 图的深度遍历算法  DFS应用
     国际象棋棋盘8*8方格棋盘,现将马放在任意指定的方格中,
     要求每个方格只能进入一次,最终使得马,走遍棋盘64个格子
    
     实现马踏棋盘的操作,要求用1-64来标注马移动的路径
    
        递归8^64 
    
    1)对于在n*n棋盘中,当n>=5且为偶数的时候,以任一点做点都有解 
    
    */
    
    #include "stdio.h"
    #include "stdlib.h"
    #include "stdbool.h"
    #include "malloc.h" 
    #include "time.h"
    
    #define X 8
    #define Y 8
    int chess[X][Y]; //定义全局变量,棋盘     
    //每种马都有八种跳法
    
    //符合马走日的规律 
    //  0 1 0 2 0
    //  8 0 0 0 3 
    //  0 0 M 0 0 
    //  7 0 0 0 4 
    //  0 6 0 5 0 
    
    //找到基于(x,y)位置的下一个可走位置 
    int Next_xy(int *x, int *y, int count)
    {
        switch(count)//注意以马为中心位置进行计算 
        {
            case(0)://3号 位置 
                if((*x+2) <= (X-1) && (*y-1) >= 0 && chess[*x+2][*y-1]==0)  //位置 [*2+1][*y-1]
                {
                    *x += 2;
                    *y -= 1;
                    return 1; 
                }break;
    
            case(1)://4号 位置
                if((*x+2) <= (X-1) && (*y+1) <= (Y-1) && chess[*x+2][*y+1]==0)  
                {
                    *x += 2;
                    *y += 1;
                    return 1; 
                }break; 
    
            case(2)://5号位置 
                if((*x+1) <= (X-1) && (*y+2) <= (Y-1) && chess[*x+1][*y+2]==0) 
                {
                    *x += 1;
                    *y += 2;
                    return 1; 
                }break;             
    
            case(3)://6号位置 
                if((*x-1) >= 0 && (*y+2) <= (Y-1) && chess[*x-1][*y+2]==0) 
                {
                    *x -= 1;
                    *y += 2;
                    return 1; 
                }break; 
    
            case(4)://7号位置 
                if((*x-2) >= 0 && (*y+1) <= (Y-1) && chess[*x-2][*y+1]==0) 
                {
                    *x -= 2;
                    *y += 1;
                    return 1; 
                }break;             
    
            case(5)://8号位置 
                if((*x-2) >= 0 && (*y-1) >=0 && chess[*x-2][*y-1]==0) 
                {
                    *x -= 2;
                    *y -= 1;
                    return 1; 
                }break;             
    
            case(6)://1号位置 
                if((*x-1) >= 0 && (*y-2) >=0 && chess[*x-1][*y-2]==0) 
                {
                    *x -= 1;
                    *y -= 2;
                    return 1; 
                }break;             
    
            case(7)://2号位置 
                if((*x+1) <= (X-1) && (*y-2) >=0 && 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]);  // /t表示跳格 
            }
            printf("\n");
        }
        printf("\n");
    }
    
    //深度优先遍历棋盘 
    //(x,y)起始位置坐标
    //tag标记变量,局部变量 
    int TravelChessBoard(int x, int y, int tag) //开始为1 每走一次tag加1 
    {
        int x1 = x, y1 = y, flag = 0, count =0;
        chess[x][y] = tag; //程序里面改动的是x,y的值,所以跟tag没啥太大关系 
    
        if( X*Y == tag )
        {
            print();//打印棋盘
            return 1; 
        } 
        flag = Next_xy(&x1, &y1, count);  //查找马的下一个可走坐标(x1,y1) ,如果找到flag=1, 否则flag =0
    
        while(flag ==0 && count<7) //一个点搜索全部可跳 
        {
            count++;
            flag = Next_xy(&x1, &y1, count);
        }
    
        while(flag)
        {
            if( TravelChessBoard(x1, y1, tag+1) )
            {
                return 1;
            } 
            //查找马的下一个可走坐标(x1,y1) ,如果找到flag=1, 否则flag =0
            x1 = x;
            y1 = y;
            count ++;
            flag = Next_xy(&x1, &y1, count);
        } 
    
        if(0 == flag)
        {
            chess[x][y] = 0;
        } 
        return 0;   
    } 
    
    
    //0-48 A-65
    int main()
    {
        clock_t start,finish;
        int i,j;
    
        for(i=0; i<X; i++)
        {
            for(j=0; j<X; j++)
            {
                chess[i][j] = 0;
            }
        }
    
    
        start = clock(); 
    
        if( !TravelChessBoard(2, 0, 1) )
        {
            printf("马踏棋盘失败!!\n");
        }
    
        finish = clock(); 
    
        printf("本次计算用时 %f\n",(double)(finish-start)/CLOCKS_PER_SEC);
    
        printf("\nhello World!\n");
        return;
    }

程序结果  
![程序结果][70]

[70]: /images/20220515/207aa0753d364fbc85faec732ee43250.png