数据结构-马走日的解法

柔情只为你懂 2022-05-19 06:46 185阅读 0赞

***【题目来自灰灰考研】***

（**2018上海交通大学上机题**）（**2017华中科技大学上机题**）

假设国际象棋棋盘有5\*5共25个格子。设计一个程序，使棋子从初始位置（如图）开始跳马，需要将棋盘的格子全部都走一遍，每个格子只允许走一次。

**问：总共有多少解。（提示：回溯法）**

**P.S国际象棋的棋子是在格子中间的。国际象棋中的“马走日”，如下图2所示，第一步为\[1,1\],第二步为\[2,8\]或\[2,12\]，第三步可以是\[3,5\]或\[3,21\]等，以此类推。**

#include<iostream>
    #include<cstdlib>
    #include<cstring>
    #define MIN 0xc0c0c0c0
    #define MAX 0x3f3f3f3f
    using namespace std;
    
    const int n = 5, m = 5;//定义问题规模 
    int count = 0;//问题解法数量 
    int map[n][m], trace[5][5], visit[5][5];//map表示整个地图，trace记录路径，visit用来记录当前点是否被走过 
    int moveDirection[][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};//下一步相对于当前位置的偏移量 
    
    void PrintTrace(int data[][m]);
    void HorseJumpSolutionNumbers(int x, int y, int steps)
    {
    	trace[x][y] = steps;
    	if(n * m == steps)//如果走的步数等于问题的规模，即找到一种解法 
    	{
    		if(count == 0)
    			PrintTrace(trace);//这路仅仅打印第一个解法的路径 
    		count++;//问题解法+ 1 
    	}
    	int nextX, nextY;
    	for(int i = 0; i < 8; i++)
    	{
    		nextX = x + moveDirection[i][0];
    		nextY = y + moveDirection[i][1];//下一步的坐标 
    		if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m)//判断坐标是否合法 
    			continue;
    		if(visit[nextX][nextY] == 0)//坐标合法且未被访问过，才进行访问 
    		{
    			visit[nextX][nextY] = 1;//访问标记为1 
    			HorseJumpSolutionNumbers(nextX, nextY, steps + 1);//以当前点为父节点，递归访问下一步 
    			visit[nextX][nextY] = 0;//以当前点为基准访问完所有子问题的解空间后，要进行回溯，所以要取消当前节点的标记 
    		}
    	}
    	
    } 
    void PrintTrace(int data[][m])
    {
    	for(int i = 0; i < n; i++)
    	{
    		for(int j = 0; j < m; j++)
    		{
    			cout<<trace[i][j]<<"\t";
    		}
    		cout<<endl;
    	 } 
    	 cout<<"==================="<<endl;
    }
    
    
    int main()
    {
    	int x, y;
    	memset(map, 0, sizeof(map));
    	memset(trace, 0, sizeof(trace));
    	memset(visit, 0, sizeof(visit));
    	x = 0;
    	y = 0;
    	visit[x][y] = 1;
    	HorseJumpSolutionNumbers(x, y, 1);
    	cout<<"共有走法："<<count<<endl; 
    	return 0;
    }