论坛 › 数据结构与算法 › 马踏棋盘问题

张林要努力啊 发表于 2020-3-22 20:55:39

马踏棋盘问题

请问为什么我这个程序跑不出来啊，一直在运行，没有结果{:10_266:} {:10_266:}
#include <stdio.h>
#include <stdlib.h>

#define X 8
#define Y 8

int chess;

int next(int *px, int *py, int count)
{
    int x=*px, y=*py;
    switch(count)
    {
      case 0:
            if(x-2>=0&&y-1>=0&&chess==0)
            {
                  *px=x-2;
                  *py=y-1;
                  return 1;
            }
            break;
      case 1:
            if(x-2>=0&&y+1<Y&&chess==0)
            {
                  *px=x-2;
                  *py=y+1;
                  return 1;
            }
            break;
      case 2:
            if(x+2<X&&y-1>=0&&chess==0)
            {
                  *px=x+2;
                  *py=y-1;
                  return 1;
            }
            break;
      case 3:
            if(x+2<X&&y+1<Y&&chess==0)
            {
                  *px=x+2;
                  *py=y+1;
                  return 1;
            }
            break;
      case 4:
            if(x-1>=0&&y-2>=0&&chess==0)
            {
                  *px=x-1;
                  *py=y-2;
                  return 1;
            }
            break;
      case 5:
            if(x-1>=0&&y+2<Y&&chess==0)
            {
                  *px=x-1;
                  *py=y+2;
                  return 1;
            }
            break;
      case 6:
            if(x+1<X&&y-2>=0&&chess==0)
            {
                  *px=x+1;
                  *py=y-2;
                  return 1;
            }
            break;
      case 7:
            if(x+1<X&&y+2<Y&&chess==0)
            {
                  *px=x+1;
                  *py=y+2;
                  return 1;
            }
            break;
      default:
            break;
    }
    return 0;
}

int sethorse(int x, int y,int tag)
{
    int x1=x,y1=y,flag=0,count=0;
    chess=tag;
    if(tag==X*Y)
    {
      return 1;
    }
    flag = next(&x1,&y1,count);
    while(flag==0&&count<7)
    {
      count++;
      flag = next(&x1,&y1,count);
    }
    while(flag)
    {
      if(sethorse(x1,y1,tag+1))
      {
                return 1;
      }
      x1=x;
      y1=y;
      count++;
      flag = next(&x1,&y1,count);
      while(flag==0&&count<7)
      {
            count++;
            flag = next(&x1,&y1,count);
      }
    }
    if(flag==0)
    {
      chess = 0;
    }
    return 0;
}

int main(void)
{
    int i, j;
      for( i=0; i < X; i++ )
      {
                for( j=0; j < Y; j++ )
                {
                        chess = 0;
                }
      }

    if(sethorse(1,0,1))
    {
      for(i=0;i<X;i++)
      {
            for(j=0;j<Y;j++)
            {
                printf("%2d   ",chess);
            }
            printf("\n");
      }
    }
    else
    {
      printf("未成功！！！");
    }
    return 0;
}

sunrise085 发表于 2020-3-22 21:19:32

哎呀，妈呀。程序太长了，
一点注释也没有。
基本没人愿意花费这么长时间去帮你看这个程序。
因为花很长时间看程序也不一定能帮你解决
即使帮你解决了对自己帮助也不会太大。
得不偿失的事情很少有人愿意去干。

张林要努力啊 发表于 2020-3-22 21:42:44

sunrise085 发表于 2020-3-22 21:19
哎呀，妈呀。程序太长了，
一点注释也没有。
基本没人愿意花费这么长时间去帮你看这个程序。


谢谢提醒，我的错{:10_262:}

张林要努力啊 发表于 2020-3-22 21:48:40

用深度优先打印出棋子的所有落脚点顺序

#include <stdio.h>
#include <stdlib.h>

#define X 8
#define Y 8

int chess;

// 找到基于(x,y)位置的下一个可走的位置
int next(int *px, int *py, int count)
{
    int x=*px, y=*py;
    switch(count)//棋子可能的8种落脚点
    {
      case 0:
            if(x-2>=0&&y-1>=0&&chess==0)
            {
                  *px=x-2;
                  *py=y-1;
                  return 1;
            }
            break;
      case 1:
            if(x-2>=0&&y+1<Y&&chess==0)
            {
                  *px=x-2;
                  *py=y+1;
                  return 1;
            }
            break;
      case 2:
            if(x+2<X&&y-1>=0&&chess==0)
            {
                  *px=x+2;
                  *py=y-1;
                  return 1;
            }
            break;
      case 3:
            if(x+2<X&&y+1<Y&&chess==0)
            {
                  *px=x+2;
                  *py=y+1;
                  return 1;
            }
            break;
      case 4:
            if(x-1>=0&&y-2>=0&&chess==0)
            {
                  *px=x-1;
                  *py=y-2;
                  return 1;
            }
            break;
      case 5:
            if(x-1>=0&&y+2<Y&&chess==0)
            {
                  *px=x-1;
                  *py=y+2;
                  return 1;
            }
            break;
      case 6:
            if(x+1<X&&y-2>=0&&chess==0)
            {
                  *px=x+1;
                  *py=y-2;
                  return 1;
            }
            break;
      case 7:
            if(x+1<X&&y+2<Y&&chess==0)
            {
                  *px=x+1;
                  *py=y+2;
                  return 1;
            }
            break;
      default:
            break;
    }
    return 0;
}


// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量，每走一步，tag+1
//用回溯法
int sethorse(int x, int y,int tag)
{
    int x1=x,y1=y,flag=0,count=0;
    chess=tag;

    // 如果tag==X*Y，则完成整个棋盘的遍历
    if(tag==X*Y)
    {
      return 1;
    }
    flag = next(&x1,&y1,count);
    while(flag==0&&count<7)
    {
      count++;
      flag = next(&x1,&y1,count);
    }
    while(flag)
    {
      if(sethorse(x1,y1,tag+1))
      {
                return 1;
      }
      x1=x;
      y1=y;
      count++;
      flag = next(&x1,&y1,count);
      while(flag==0&&count<7)
      {
            count++;
            flag = next(&x1,&y1,count);
      }
    }
    if(flag==0)
    {
      chess = 0;
    }
    return 0;
}

int main(void)
{
    int i, j;

//初始二维数组
      for( i=0; i < X; i++ )
      {
                for( j=0; j < Y; j++ )
                {
                        chess = 0;
                }
      }


    if(sethorse(1,0,1))//如果函数返回值为1，则打印棋盘
    {
      for(i=0;i<X;i++)
      {
            for(j=0;j<Y;j++)
            {
                printf("%2d   ",chess);
            }
            printf("\n");
      }
    }
    else
    {
      printf("未成功！！！");
    }
    return 0;
}

张林要努力啊 发表于 2020-3-22 21:50:48

其实大部分跟小甲鱼的一样，不过打印棋盘我放在了main函数里，然后棋子的8种落脚点跟小甲鱼的不一样

wuhao4221961 发表于 2020-3-23 09:07:38

慢慢来最快

六小鸭 发表于 2020-3-24 07:49:01

我来了
鱼币
{:10_277:}

永远的渣滓 发表于 2020-3-24 10:45:37

yubi

璀璨·狸 发表于 2020-4-1 08:18:38

张林要努力啊 发表于 2020-3-22 21:48
用深度优先打印出棋子的所有落脚点顺序

#include


谢谢楼主

珂乔乔 发表于 2020-4-1 19:28:31

完全看不懂。。。。。

winsome8538 发表于 2020-4-1 19:29:47

巨长。。。。。。。。。。。。。。。。。。

依可儿 发表于 2020-4-1 19:31:04

不知道要学到什么程度才能看懂。。。。

majian890324 发表于 2020-4-30 21:05:14

完全看不懂。。。。。

lijiachen 发表于 2020-5-13 18:06:23

鱼币~~

查看完整版本: 马踏棋盘问题