Re: 請問一下啊.....

※ 引述《gogo (gogo)》之銘言：
: ※ 引述《[email protected] (心情不定..)》之銘言：
: : 請問一下有誰會寫騎士漫遊的啊.....
: :     就是棋盤的每個格子都要走過..不能重覆..
: :     要用C++的方式..還要有註解啊..
: :     請各位高手幫一下忙......謝謝啊..
: 有一個想法..
: 先走玩外圈在往內走
: 比較容易找解
Source
好久前的.. 用 C 寫的.. 自己改囉
#include <stdlib.h>
#define SWAP( x, y, t) ( (t) =(x), (x) =(y), (y) =(t) )
#define  Window 8

int count =0;
int solution_count =0;

struct direction
      {int x;
       int y;
      }dir[8];
struct direction dir[8] ={{ 1,-2},{ 2,-1},{ 2, 1},{ 1, 2},
                          {-1, 2},{-2, 1},{-2,-1},{-1,-2}};
static int wind[Window][Window];

struct windows {
        int x;
        int y;
      };

struct gogo
   {
     int x ,y, loop;
   }temp_loop[8];

void Quick_Sort (int left, int right)
{
 int i, j, key, temp;
   if (right > left) {
    key =temp_loop[right].loop;
    i =left -1;
    j =right;
     while(1) {
      while( temp_loop[++i].loop <key);
      while( temp_loop[--j].loop >key);
      if(i > j) break;
        SWAP(temp_loop[i].loop, temp_loop[j].loop, temp);
        SWAP(temp_loop[i].x, temp_loop[j].x, temp);
        SWAP(temp_loop[i].y, temp_loop[j].y, temp);
     }
        SWAP(temp_loop[i].loop, temp_loop[right].loop, temp);
        SWAP(temp_loop[i].x, temp_loop[right].x, temp);
        SWAP(temp_loop[i].y, temp_loop[right].y, temp);
    Quick_Sort( left, i-1);
    Quick_Sort( i+1, right);
   }
}

int  how_many_loot_of_the_next_next_move(int x, int y)
{
 int i, j =0, x1, y1;
 if(x >=0 && x <Window && y >=0 && y <Window && wind[x][y]==0) {
    for(i =0; i <8; i++) {
         x1 =x +dir[i].x;
         y1 =y +dir[i].y;
    if( x1 >=0 && x1 <Window && y1 >=0 && y1 <Window && wind[x1][y1] ==0)
     j ++;
    }
     return j;
  }
 else
   return 10;
}

struct windows select_next(int x, int y,int *loop, int direct)
{
 int i;
 struct windows windows;
 for(i =0; i <8; i++) {
  temp_loop[i].loop =how_many_loot_of_the_next_next_move(x+dir[i].x,y+dir[i].y);
  temp_loop[i].x =x+dir[i].x;
  temp_loop[i].y =y+dir[i].y;
  }
  Quick_Sort(0 ,7);
    *loop =temp_loop[direct].loop;
    windows.x = temp_loop[direct].x;
    windows.y = temp_loop[direct].y;
  return windows;
}

void listout(void)
{
 int i ,j;
 char key;
 printf("%d th solution path  (press 'q' to exit,'p' to stop)\n",
            solution_count+1);
 for (i =0; i <Window; i++) {
   for (j =0; j <Window; j++) {
      printf("%4d",wind[j][i]);
    }
  printf("\n");
}
 printf("More ....\n");
}

void cant_move_or_not(void)
{
 if(count < 0) {
       printf("it cant move over");
       exit(0);
       }
}

/* the main function in this program */
void Next_move(int x, int y, int loop)
{
   int i,temp,key;
   struct windows windows;
     cant_move_or_not();
     wind[x][y] =(++count);
      for(i =0; i<loop; i++)  {
           windows =select_next(x, y, &temp, i);
           Next_move(windows.x ,windows.y, temp);
         }
      if(count == Window*Window) {
          listout();
          solution_count++;
         /* scanf("%c",&key); */
         /* if(solution_count > 20)
              exit(1);  */
        /*  if(key =='q')
              exit(1);  */
        }
      count--;                           /* back  */
      wind[x][y] =0;
}
void main(void)
{
 /*int x, y;
 printf("Enter where do you want to put (this array is %d*%d):",
         Window,Window);
 scanf("%d%d",&x,&y);
 while(x <0 || x >Window || y <0 || y> Window) {
  printf("Warning,   Please input correct move (example 0 0):");
  scanf("%d%d",&x,&y);
 }*/
 Next_move(0, 0, 2);
 printf("total solution is %d", solution_count);
}
--
   ※發信站: 漢神小站 <bbs.ee.nsysu.edu.tw> 
    ◆ From: jasmine.ee.nsysu.edu.tw