kinghtchf.c

《数据结构-使用C语言》第三版

/*
对于本题,一般可以采用回溯法,这里采用Warnsdoff策略求解,这也是一种贪婪法,
其选择下一出口的贪婪标准是在那些允许走的位置中,选择出口最少的那个位置。
如马的当前位置（i,j）只有三个出口,他们是位置（i+2,j+1）、（i-2,j+1）和
（i-1,j-2）,如分别走到这些位置,这三个位置又分别会有不同的出口,假定这三
个位置的出口个数分别为4、2、3,则程序就选择让马走向（i-2,j+1）位置。   
    
由于程序采用的是一种贪婪法,整个找解过程是一直向前,没有回溯,所以能非常
快地找到解。但是,对于某些开始位置,实际上有解,而该算法不能找到解。对于
找不到解的情况,程序只要改变8种可能出口的选择顺序,就能找到解。改变出口
选择顺序,就是改变有相同出口时的选择标准。以下程序考虑到这种情况,引入变
量start,用于控制8种可能着法的选择顺序。开始时为0,当不能找到解时,就让
start增1,重新找解。细节以下程序。
*/

#include <stdio.h>

#define INF 9999999

int board[9][9];
int start;
int mover[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int movec[] = {1, 2, 2, 1, -1, -2, -2, -1};

int main()
{
 	int next(int r, int c);
 	int ber, bec;
 	int step, test;
 	int r, c;
 	int i, j, k;
 	while(scanf("%d%d", &ber, &bec) != EOF)
	{
  		start = 0;
        test = 1;
  		while(start <= 7)
		{
   			for(i = 0;i <= 7;i++)
    		for(j = 0;j <= 7;j++)
     		board[i][j] = 0;
   			r = ber;
   			c = bec;
   			board[r][c] = 1;
   			step = 2;
   			while(1)
			{
    			if(step > 64)
				{
     				printf("Case %d:\n", test++);
     				for(i = 0;i <= 7;i++)
					{
     		 			for(j = 0;j <= 7;j++)
       					printf("%d ", board[i][j]);
      					printf("\n");
     				}
     				printf("\n");
     				start++;
    		 		break;
    			}    
    			k = next(r, c);
    			if(k == -1)
				{
     				start++;
    	 			break;
    			}
    			r = r + mover[k];
    			c = c + movec[k];
    			board[r][c] = step;
    			step++;
   			}
  		}
 	}
 	return 0;
}

int next(int r, int c)
{/*返回下次要查找的增量，若为-1则没有可以查找的位置*/
 	int numable(int r, int c, int nexta[]);
 	int number(int r, int c);
 	int nexta[20], num, num1 = 0, minnum, i, k;
 	minnum = INF;
 	num = numable(r, c, nexta);
 	if(num == 0) return -1;  //没有出口 
 	for(i = 0;i <= num - 1;i++)
	{
  		num1 = number(r + mover[nexta[i]], c + movec[nexta[i]]);
  		if(num1 <= minnum)
		{
   			minnum = num1;
   			k = nexta[i];
  		}
 	}
 	return k;
}

int numable(int r, int c, int nexta[])
{/*返回下次可以查找的增量*/
 	int i, k, a, b;
 	int num = 0;
 	for(i = 0;i <= 7;i++)
	{
 		k = (i + start) % 8;
  		a = r + mover[k];
  		b = c + movec[k];
        if(a <= 7 && a >= 0 && b >= 0 && b <= 7 && board[a][b] == 0)
		{
   			nexta[num] = k;
   			num++;
  		}
 	}
 	return num;
}

int number(int r, int c)
{/*返回下次可以查找的增量的个数*/
 	int i, k, a, b;
 	int num = 0;
 	for(i = 0;i <= 7;i++)
	{
  		k = (i + start) % 8;
  		a = r + mover[k];
  		b = c + movec[k];
        if(a <= 7 && a >= 0 && b >= 0 && b <= 7 && board[a][b] == 0)
   		num++;
 	}
 	return num;
}