淘先锋技术网

首页 1 2 3 4 5 6 7

将马随机放在国际象棋的Board[0~7]的某个方格中,马按走棋规则进行移动。,走遍棋盘上全部64个方格。编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入一个8×8的方阵,输出之。

在外层另外加上两层,确保 8*8 方格中的每一个格子都有8中不同的选择;
重点:为了确保每个格子能走日字,而且选择的可能性等同,初始化除了最外两层格子标记没有被访问,最外两层中每个格子都标记为已被访问即可达到目标!
重点是记录每一个走过的点的坐标和他是第几个方向,如果下一个点满足条件,继续压栈,如果不可以,再回到这个点,让i取下一个方向继续搜索。

#include <iostream>
#include <cstdio>
using namespace std;

int stackhorse[100][3]={0};//[i][0]和[i][1]是x,y,[i][2]是当前第i个方向 
int chess[12][12]={0};
int count=1;
int next[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},\
				{-1,-2},{1,-2},{2,-1}};

void printchess();
void horse(int x, int y);

int main()
{
	for (int i=0; i<12; i++)
		for (int j=0; j<12; j++)
			if (i==0||i==1||i==10||i==11||j==0||j==1||j==10||j==11)
				chess[i][j]=-1;
	horse(2, 2);//相当于[0][0]
	printchess();
	return 0;
}

void horse(int x, int y)
{
	int top=0, i=0;
	int tx, ty;
	chess[x][y]=count; 
	
	stackhorse[top][0]=stackhorse[top][1]=2;
	while (count<64){
		for (i; i<8; i++){//i不能初始化 
			tx=x+next[i][0];
			ty=y+next[i][1];
			if (chess[tx][ty]==0)//如果没走过,break 
				break; 
	 	}
		if (i<8){
			count++;
			chess[tx][ty]=count;
			stackhorse[top][2]=i;
			top++;//新点入栈 
			stackhorse[top][0]=tx;
			stackhorse[top][1]=ty;
			x=tx;
			y=ty;
			i=0; 
		}else{//这个点八个方向都不满足条件,退回上一个点 
			count--;
			chess[x][y]=0;
			top--;
			x=stackhorse[top][0];
			y=stackhorse[top][1];
			i=stackhorse[top][2];
			i++; //下一个方向 
		} 
	}
}

void printchess()
{
	for (int i=2; i<=9; i++){
		for (int j=2; j<=9; j++){
			printf("%4d", chess[i][j]);
		}
		printf("\n");
	}
}