论坛 › 数据结构与算法 › 骑士周游问题C语言

gaopool 发表于 2022-11-22 16:05:40

骑士周游问题C语言

#include<stdio.h>
#include<time.h>

#define X 8
#define Y 8

int chess;

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

    return 0;
}







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

gaopool 发表于 2022-11-22 16:07:41

本帖最后由 gaopool 于 2022-11-22 16:14 编辑

我已经去掉那个case6了，但还是有问题

查看完整版本: 骑士周游问题C语言