求帮忙看看马踏棋盘算法哪里错了。,数据结构与算法,技术交流,鱼C论坛

gascd 发表于 2017-1-26 12:15:46

求帮忙看看马踏棋盘算法哪里错了。

本帖最后由 gascd 于 2017-1-26 12:26 编辑

代码和小甲鱼的对照了，除了nextxy()函数以外，其他的函数都差不多。然而我的nextxy()函数就算不出解来，而小甲鱼的nextxy()函数就能够算出来。
如下为代码:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define X 8
#define Y 8

int chess;

#if 0
//小甲鱼的正确的代码
int nextxy(int *x, int *y, int count)
{
switch(count)
{
case 0:
if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
{
*x = *x + 2;
*y = *y - 1;
return 1;
}
break;

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;
}
break;

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

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;
}
break;

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

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

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

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

default:
break;
}

return 0;
}
#endif

#if 1
//我的错误代码
// 判断下一步能不能走
int nextxy(int *x, int *y, int count)
{
switch(count)
{
case 0:if((*x)-1>=0 && (*y)+2<=Y-1 && chess[*x-1][*y+2]==0)
   {
   *x = (*x)-1;
   *y = (*y)+2;
   return 1;
   } break;
case 1:if((*x)+1<=X-1 && (*y)+2<=Y-1 && chess[*x+1][*y+2]==0)
{
*x = (*x)+1;
*y = (*y)+2;
return 1;
   } break;
case 2:if((*x)+2<=X-1 && (*y)+1<=Y-1 && chess[*x+2][*y+1]==0)
   {
   *x = (*x)+2;
   *y = (*y)+1;
   return 1;
   }break;
case 3:if((*x)+2<=X-1 && (*y)-1>=0 && chess[*x+2][*y-1]==0)
{
*x = (*x)+2;
*y = (*y)-1;
return 1;
   } break;
case 4:if((*x)+1<=X-1 && (*y)-2>=0 && chess[*x+1][*y-2]==0)
   {
   *x = (*x)+1;
   *y = (*y)-2;
   return 1;
   } break;
case 5:if((*x)-1>=0 && (*y)-2>=0 && chess[*x-1][*y-2]==0)
   {
   *x = (*x)-1;
   *y = (*y)-2;
   return 1;
   } break;
case 6:if((*x)-2>=0 && (*y)-1>=0 && chess[*x-2][*y-1]==0)
   {
   *x = (*x)-2;
   *y = (*y)-1;
   return 1;
   } break;
case 7:if((*x)-2>=0 && (*y)+1<=Y-1 && chess[*x-2][*y+1]==0)
{
*x = (*x)-2;
*y = (*y)+1;
return 1;
   } break;
default:break;
}
return 0;
}
#endif

void print()
{
int i, j;
for(i=0; i<X; i++)
{
for(j=0; j<Y; j++)
{
printf("%2d\t", chess);
}
printf("\n");
}
}

//深度优先遍历
//(x,y)为位置坐标
//tag是标识变量,每走一步tag+1
int TravelChessBoard(int x, int y, int tag)
{
int x1, y1, flag, count;
x1 = x;
y1 = y;
flag = count = 0;
chess = tag;

//判断是否走完
if(X*Y == tag)
{
print();
return 1;
}
//判断下一步能不能走,能flag = 1
flag = nextxy(&x1, &y1, count);
while(0 == flag && count < 8)
{
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 < 8)
{
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("\nsorry,马踏棋盘失败!\n");
finish = clock();
printf("\n本次计算时间为%lf秒\n",(double)(finish-start)/CLOCKS_PER_SEC);

system("pause");
return 0;
}

gascd 发表于 2017-1-28 21:54:08

不是哪里错了，而是我的nextxy()函数里,case的顺序不同，导致了算法的时间大大大大大大的增加。大约需要一个多月算出来！！！！！！！！
咳咳，其实只要换个简单的点，就可以了，或者改一下case顺序。
总之，错的人不是我，错的是……这个时间太长了。

Code_mzh 发表于 2018-2-18 22:50:54

gascd 发表于 2017-1-28 21:54
不是哪里错了，而是我的nextxy()函数里,case的顺序不同，导致了算法的时间大大大大大大的增加。大约需要一 ...

我的也是，不知道为啥nextxy顺序不对就会出错呢，这是什么原理，求大神解答

gascd 发表于 2018-3-18 00:57:29

Code_mzh 发表于 2018-2-18 22:50
我的也是，不知道为啥nextxy顺序不对就会出错呢，这是什么原理，求大神解答

这个我搞懂了。因为nextxy顺序不对，所以马儿还在一步一步的试着跳。直到把正确的路径给找出来。这个过程需要很长的时间。

页: [1]

鱼C论坛's Archiver

求帮忙看看马踏棋盘算法哪里错了。