jump.cpp

C++Example实用的算法:包括枚举

//回溯法
//跳马问题
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>

#define ROW  4
#define LINE 8
#define NUM  ROW*LINE
//结点结构
struct{
	int index;   //方向的索引
	int step;    //行到的步数
	int pre;     //标志前一步的位置
}array[ROW][LINE];

int begin_row,begin_line; //起始位置

//定义八个循环方向
static int direct[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};

//判断是否符合走法规则，如果符合，则往下走
//index为-1表示没有走到过,其他表示下一个走的方向
int Check(int& row , int& line , int step){
	int next_row , next_line;
	array[row][line].step = step;
	for(int index = array[row][line].index + 1 ; index < 8 ; index++){
		next_row = row + direct[index][0];
		next_line = line + direct[index][1];
		if( next_row >= 0 && next_row < ROW &&
			next_line >= 0 && next_line < LINE &&
			array[next_row][next_line].index == -1 )
			break;
	}
	//当所有的可能结束时返回标记
	if(index == 8 && row == begin_row && line == begin_line )
		return 9;
	//当某个结点(不包括开始点)的可能结束时返回
	if(index == 8 )
		return -1;
	array[next_row][next_line].pre = index;
	array[row][line].index = index;
	row = next_row;
	line = next_line;
	return index;
}
//回退到上个结点的函数
void back(int& row,int& line){
	int pre_row , pre_line;
	array[row][line].index = -1;
	pre_row = row -  direct[array[row][line].pre][0];
	pre_line = line - direct[array[row][line].pre][1];
	row = pre_row;
	line = pre_line;
}
int main(){
	int row , line;
	int index;
	int total = 0;

	cout<<"输入初始行与列"<<endl;
	cin>>begin_row>>begin_line;

	row = begin_row ;
	line = begin_line ;
	//初始化各结点
	for(int i = 0 ; i < ROW ; i++)
		for(int j = 0 ; j < LINE ; j++){
			array[i][j].index = -1;
			array[i][j].step = 0;
			array[i][j].pre = 0;
		}
	//以步数进行循环，成功则打印出来
	for(int num = 1 ; num <= NUM ; num++){
		index = Check( row , line , num);
		if( index == 9 )
			break;
		if( index == -1 && num == NUM ){
			//可以选择是否打印结果
			for(int i = 0 ; i < ROW ; i++){
				for(int j = 0 ; j < LINE ; j++)
					cout<<setw(4)<<array[i][j].step;
				cout<<endl;
			}
			cout<<endl;
			getch();
			total++;
		}
		if( index == -1 ){
			num -= 2;
			back(row , line);
		}
	}
	cout<<"总共的可能走法数：  "<<total<<endl;
	return 0;
}