C语言-数据结构-骑士周游-马踏棋盘问题-源代码

系统管理员 2022-07-14 08:40 159阅读 0赞

**1. 目标**

对于一个指定的起始坐标，按照‘马’的走棋规则，从该坐标开始搜索一条可以覆盖棋盘每个位置的走棋路径。例如下面是从（2，0）坐标开始搜索得到的一个解。

![Center][]

**2. 代码结构**

![Center 1][]

**3. 源代码**

该代码仅仅是寻找到一条生路，即停止。另外对选择的起始点，和寻找下一点的顺序不同（即sposition()中case的顺序不同，对于程序执行的时间影响会很大）。

另外程序中调用了time.h头文件中的clock相关函数，对代码的执行时间进行了统计，具体见代码。

#include<stdio.h>
    #include<time.h>
    #define title "------------------------------Life is a fight!------------------------------------"
    #define X 8 //定义棋盘大小
    #define Y 8
    
    int chess[X][Y]= {
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0}
                  };
    
    int sposition(int *x, int *y, int p)
    {
    
        switch(p)//特别需要注意每个case 中的顺序，对程序执行的时间有很大影响
    	{
    		case 0:
    			if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
    			{
    				*x = *x + 2;
    				*y = *y - 1;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 1:
    			if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
    			{
    				*x = *x + 2;
    				*y = *y + 1;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 2:
    			if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
    			{
    				*x = *x + 1;
    				*y = *y - 2;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 3:
    			if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
    			{
    				*x = *x + 1;
    				*y = *y + 2;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 4:
    			if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
    			{
    				*x = *x - 2;
    				*y = *y - 1;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 5:
    			if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
    			{
    				*x = *x - 2;
    				*y = *y + 1;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 6:
    			if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
    			{
    				*x = *x - 1;
    				*y = *y - 2;
    				return 1;
    			}
    			else
                    return 0;
    
    		case 7:
    			if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
    			{
    				*x = *x - 1;
    				*y = *y + 2;
    				return 1;
    			}
    			else
                    return 0;
    
    		default:
    			return 0;
    	}
    }
    
    void prfChess(int t_chess[][Y])
    {
        int i, j;
        for(i=0;i<X;i++)
        {
            for(j=0;j<Y;j++)
            {
                printf("%3d", t_chess[i][j]);
            }
            printf("\n");
        }
    }
    
    
    int searchp(int x, int y, int c)
    {
        int x1, y1, p=0;
        int i, j, flag=0;
    
        x1=x; y1=y;
    
        chess[x1][y1]=c;
        //printf("%d\n",c);
    
        if(X*Y==c)  //递归结束条件
        {
            prfChess(chess);
            return 1;
        }
    
        flag=sposition(&x1, &y1, p);//找到第一个符合条件的位置
        while(0==flag && p<X-1)
        {
            p++;
            flag=sposition(&x1,&y1,p);
        }
    
        while(flag) //如果不是死路，即存在往下走的位置
        {
            if(searchp(x1,y1,c+1))    //继续往下搜索，直到满足c==X*Y,返回1，结束递归
                return 1;
    
            x1=x;   //如果是死路一条，则要向后退，回溯到上一个位置
            y1=y;
    
            p++;    //将P向后移一个位置，继续搜索其他的可能位置
            flag=sposition(&x1,&y1,p);
            while(0==flag && p<X-1)
            {
                flag=sposition(&x1,&y1,++p);
            }
        }
    
    
        if(0==flag) //如果经过搜索，没有满足条件的位置，则将该位置的值改回去，变为零
        {
           chess [x][y]=0;
        }
        return 0;
    }
    
    int main(void)
    {
        clock_t start, end;
        double t;
        printf("%s\n\n\n",title);
        start=clock();
        if(!searchp(2,0,1))
            printf("Cannot find!!!\n\n\n");
        end=clock();
        t=(double)(end-start)/CLOCKS_PER_SEC;
        printf("\nUsed %f seconds\n\n\n", t);
        return 0;
    }

[Center]: /images/20220714/2a8fd596be624205829176f681dd07dd.png
[Center 1]: /images/20220714/d956436b1f5346259e1170567cda37b0.png