简单搜索--马的走法

描述

        在一个4*5的棋盘上，输入马的起始位置坐标（纵、横），求马能返回初始位置的所有不同走法的总数（马走过的位置不能重复,马走“日”字）。

输入

多个测试数据。 每组2个数，表示起始位置坐标。

输出

输出不同走法的总数。

样例输入

2 2
1 3

样例输出

4596
4772

这道题可以直接用典型的DFS算法，把上下左右的方向换成马走法的规则就行。

代码：

#include<iostream>
using namespace std;
int a, b;
bool vis[5][6];//用来记录已经走过的位置
int num;
void DFS(int x, int y)
{
	int M = 0;
	int tx, ty;
	int next[8][2] = { {2,1},{2,-1},{-2,1},{-2,-1},{1,-2},{-1,-2},{-1,2},{1,2} };//马的做法的八个方向
	for (int k = 0; k < 8; k++)
	{
		//当前马可走的下一个位置
		tx = x + next[k][0];//横坐标
		ty = y + next[k][1];//纵坐标
		if (tx == a&&ty == b)//当回到原点时，可行方案+1
			num++;
		//判断是否可以走下一步
		else if (!vis[tx][ty]&&tx>=1&&tx<=4&&ty>=1&&ty<=5)
		{
			vis[tx][ty] = true;
			DFS(tx, ty);
			vis[tx][ty] = false;//当返回时需要把它从已经走过的位置中撤掉
		}
	}
}
int main()
{
	while (cin >> a >> b)
	{
		num = 0;
		memset(vis, false, sizeof(vis));
		vis[a][b] = true;//标志原位置已经走过
		DFS(a, b);
		cout << num << endl;
	}
	return 0;
}