学步园

马的走法

Time Limit:1000MS  Memory Limit:65536K
Total Submit:32 Accepted:12

Description

在一个4*5的棋盘上，马的初始位置坐标（纵 横）位置由键盘输入，求马能返回初始位置的所有不同走法的总数（马走过的位置不能重复，马走“日”字）。如果马的初始位置坐标超过棋盘的边界，则输出ERROR。例如初始位置为4 6，则输出ERROR。

Input

输入数据只有一行，有两个用空格分开的整数，表示马所在的初始位置坐标。首行首列位置编号为（1 1）。

Output

输出一行，只有一个整数，表示马能返回初始位置的所有不同走法的总数。

如果输入的马的初始位置超出棋盘边界，则输出ERROR。

Sample Input

2 2

Sample Output

4596

这是一道简单的搜索题，刚开始学习搜索，也想不出方法。找了代码慢慢理解。


基本方法是回溯，用一个二维数组来记录棋盘的当前状态，为0则未走过，为1则走过。


开始时将起点置1，试八个方向是否能走，能就置1再继续，

一旦发现已回到出发点则走法总数加1。


比较好理解。
#include <iostream>
#include <cstring>
using namespace std;

const int ROWS = 4;
const int COLUMS = 5;

int chess[ROWS][COLUMS];
int numCount;
int posX, posY;
int direction[2][8] = { {-1, -1, -2, -2, 2, 2, 1, 1}, 
			{-2, 2, 1, -1, 1, -1, 2, -2} };

void solve(int x, int y)
{
	int i, desX, desY;

	for (i = 0; i < 8; ++i)
	{
		desX = x + direction[0][i];
		desY = y + direction[1][i];
		if (desX >= 0 && desX < 4 && desY >= 0 && desY < 5
		    && chess[desX][desY] == 0)
		{
			chess[desX][desY] = 1;
			solve(desX, desY);
			chess[desX][desY] = 0;
		}
		else if (desX == posX && desY == posY)
		{
			numCount++;
		}
	}
}

int main()
{
	cin >> posX >> posY;

	if (posX < 1 || posX > 4|| posY < 1 || posY > 5)
	{
		cout << "ERROR/n";
	}
	else
	{
		posX--;
		posY--;
		memset(chess, 0, sizeof(chess));
		numCount = 0;
		chess[posX][posY] = 1;
		solve(posX, posY);
		cout << numCount << endl;
	}
	return 0;
}