首页 > 代码库 > 马踏棋盘算法递归+回溯法实现 C语言

马踏棋盘算法递归+回溯法实现 C语言

r为矩阵的行,c为矩阵的列

将结果输出到当前目录下的results.txt(需要提前建好)。

 

结果将给出:1.是否存在路径使马可以按要求走遍所有的方格;

2.解的总数;

3.程序执行的时间;

    #include<stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define r 2
    #define c 4

    int flag[r][c]={0};//存放马跳路径的二维数组
    int arr[r][c]={0};
    int x[8]={2,1,-1,-2,2,1,-1,-2};  
    int y[8]={1,2,2,1,-1,-2,-2,-1};  
    int n=1,count;
    FILE *fp;

    //初始化文件输出流
    int initOut()  
    {   
        fp=fopen("results.txt","w");  //记得关闭
        if(fp==NULL)  
        {  
            printf("File cannot open! " );  
            exit(0);  
        }
        return 0;  
    }
    
    //添加一个判断函数,判断这样的哈密顿路径是否存在
    void judgeExistence(){
        if(count==0)
            printf("%d * %d 的棋盘不存在能使得马可以不重复遍历完棋盘中每一格的路径\n",r,c);
    }

    //输出马跳的步骤stepOut()
    void stepOut(){
                for(int a=0;a<r;a++){  
               for(int b=0;b<c;b++)  
                   { 
                    fprintf(fp,"%3d ",arr[a][b]);  
                   }    
               fprintf(fp,"\n");  
            }  
          fprintf(fp,"\n");  
    }

    
    void DFS(int i,int j)
    {  
        if(n==r*c)  
        {  
            count++;  
            stepOut();//写个函数,输出马跳的步骤stepOut()
        }
        
        else
          for(int k=0;k<8;k++)  
          {  
            if(i+x[k]>=0&&i+x[k]<r&&j+y[k]>=0&&j+y[k]<c&&flag[i+x[k]][j+y[k]]==0)  
            {   
                flag[i+x[k]][j+y[k]]=1;n++;
                arr[i+x[k]][j+y[k]]=n;//给记录马跳步骤的矩阵赋值
                
                DFS(i+x[k],j+y[k]);//循环+递归
                
                flag[i+x[k]][j+y[k]]=0;n--;
            }  
        }
    }  

    void main()  
    {  
        clock_t start, finish;  //计算程序一共花费了多少时间
        long duration;
        start=clock();
        
        count=0;  
        int X,Y;
        label_1:printf("请输入马初始横坐标(X<=%d):X=\n",r);
        scanf("%d",&X);
        if(X>r){
            printf("请输入小于等于%d的数\n",r);
            goto label_1;
        }
        label_2:printf("请输入马初始纵坐标(Y<=%d):Y=\n",c);
        scanf("%d",&Y);
        if(Y>c){
            printf("请输入小于等于%d的数\n",c);
            goto label_2;
        }
        X=X-1;
        Y=Y-1;
        flag[X][Y]=1;
        arr[X][Y]=1;

        initOut();
        DFS(X,Y);
        judgeExistence();
        fprintf(fp,"解的总数为:%d\n",count); 

        finish=clock();
        duration=finish-start;//程序执行的时间,单位毫秒
        fprintf(fp,"程序执行的时间为:%10ld ms\n",duration); 
        fclose(fp); 
    }

代码中有哪些不正确的地方欢迎大家指正。

 

马踏棋盘算法递归+回溯法实现 C语言