鱼C论坛

 找回密码
 立即注册
查看: 82|回复: 1

骑士周游问题C语言

[复制链接]
发表于 2022-11-22 16:05:40 | 显示全部楼层 |阅读模式
10鱼币
#include<stdio.h>
#include<time.h>

#define X 8
#define Y 8

int chess[X][Y];

int nextxy(int *x,int *y,int count)
{
    switch(count)
    {
        case 0:
        if(*x-2>=0 && *y-1>=0 &&  chess[*x+2][*y-1]==0)
        {
            *x -= 2;
            *y -= 1;
            return 1;
        }
        break;

        case 1:
            if (*x-2>=0 && *y+1<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x -= 2;
                *y += 1;
                return 1;
            }
            break;

         case 2:
            if (*x-1>=0 && *y+2<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x -= 1;
                *y += 2;
                return 1;
            }
            break;

             case 3:
                if (*x+1<=X-1 && *y+2<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x += 1;
                *y += 2;
                return 1;
            }
            break;

        case 4:
                if (*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x += 2;
                *y += 1;
                return 1;
            }
            break;
        
        case 5:
                if (*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y+1]==0)
            {
                *x += 2;
                *y -= 1;
                return 1;
            }
            break;

        case 6:
                if (*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x += 2;
                *y += 1;
                return 1;
            }
            break;

        case 7:
                if (*x+1<=X-1 && *y-2<=Y-1 && chess[*x+2][*y+1]==0)
            {
                *x += 1;
                *y -= 2;
                return 1;
            }
            break;

        case 8:
                if (*x-1>=0 && *y-2>=0 && chess[*x+2][*y+1]==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+1
int TravelChessBoard(int x,int y,int tag)
{
    int x1 = x, y1 = y, flag = 0, count = 0;
    chess[x][y] = tag;

    if(X*Y == tag)
    {
        print();
        return 1;
    }

    //找到马的下一个可走的坐标(x1,y1),若找到flag=1反之flag=0
    flag = nextxy(&x1,&y1,count);
    while (0==flag && count<7)
    {
        count ++;
        flag = nextxy(&x1,&y1,count);
    }

    while (flag)
    {
        if(TravelChessBoard(x1,y1,tag+1))
        {
            return 1;
        }

        //继续找马的下一步可走坐标,同上
        x1 = x;
        y1 = y;
        count ++;

        flag =nextxy(&x1,&y1,count);
        while (0==flag && count<7)
        {
            count ++;
            flag = nextxy(&x1,&y1,count);
        }
    }
    if (0==flag)
    {
        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( !TravelChessBoard(2, 0, 1) )
        {
            printf("抱歉,失败咯!\n");
        }
        finish = clock();
        printf("\n本次计算耗时:%f秒\n\n",(double)(finish-start)/CLOCKS_PER_SEC);
    }

    return 0;
}







想知道这个case的顺序应该不会影响结果吧,但并不是很清楚代码问题在哪里出错了

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2022-11-22 16:07:41 | 显示全部楼层
本帖最后由 gaopool 于 2022-11-22 16:14 编辑

我已经去掉那个case6了,但还是有问题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2022-12-5 09:33

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表