dfs 马踏棋盘

Posted on |

马踏棋盘
5*5棋盘 从(0,0)按马字走步，填满整个棋盘可能的方案数

VOID DFS(状态 A)
判断当前的状态是否合法。合法则继续执行，否则则回到上次调用。
进行一次状态转移，也就是调用DFS(状态 A + Δ)

试探节点A
A是否在图（树）中
如果在 标记A
如果已被试探过的话 所影响的各种值
紧跟着去试探所有A可达的节点
等待所有的执行完后 还原标记A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
using namespace std;

int cnt = 0;
int vis[5][5];

/// 打印结果
void print()
{
	printf("Case #%d:\n", ++cnt);
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 4; j++)
			printf("%4d", vis[i][j]);
		printf("%4d\n", vis[i][4]);
	}
	printf("\n");
}

/// 判断 x 是否在范围 [l, r) 内
inline bool inbound(int x, int l, int r) { return l <= x && x < r; }

/// 深度优先搜索棋盘
///@param x 坐标x
///@param x 坐标x
///@param n 第n步
void dfs(int x, int y, int n)
{
	if (vis[x][y] == 0//判断当前位置是否合法 合法则继续进行 否则回到上次调用 
		&& inbound(x, 0, 5) && inbound(y, 0, 5)
		&& n <= 25)
	{
		vis[x][y] = n;
		n++;
		if (n > 25)
			print();//找到基于x y下一个可走的位置 
		dfs(x + 1, y + 2, n);
		dfs(x + 1, y - 2, n);
		dfs(x - 1, y + 2, n);
		dfs(x - 1, y - 2, n);
		dfs(x + 2, y + 1, n);
		dfs(x + 2, y - 1, n);
		dfs(x - 2, y + 1, n);
		dfs(x - 2, y - 1, n);
		vis[x][y] = 0;//可以回溯 
	}
	else return;
}

int main()
{
	dfs(0, 0, 1);
	return 0;
}

补充

和深搜不同，广搜总是每次都把离上一状态最近的状态用一个队列记录下来；
记录之后，检查队列是否为空，如果不为空，就讲队首元素弹出，并且以这个状态为“根节点”进行广度优先搜索。
直到整个队列为空为止。