poj 2488 A Knight's Journey 马踏棋盘 dfs

缘起

马踏棋盘可以说是最经典的dfs问题了, 突然发现我的博客里面竟然没有~ QAQ poj 2488 A Knight’s Journey

分析

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
给你一个p×q的棋盘（p×q<26）,问一匹马按照中国象棋马的走法不重复的走完所有点的路径是什么
如果有多条路径，输出字典序最小的那个。
如果没有，输出impossible。

【输入】
多样例. 第一行是样例数. 每个样例首先是p、q(1 <= p * q <= 26),表示p*q的棋盘。p是行,表示有p行数字
q表示有q个字母（列）.

【输出】
按样例输出

【样例输入】
3
1 1
2 3
4 3

【样例输出】
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

【限制】
1s

首先注意到一点——因为遍历嘛~ 你总要经过A1的（如果遍历路径存在的话）. 而又要输出字典序最小解. 所以一定是从A1搜起即可. 而因为要输出字典序最小. 所以每次开拓搜索路径的时候要将下一步按照字典序排序,按照字典序升序搜索即可.

注意，对于只需要求一个解的情形，我原先想过如何优化dfs. 优化的方式就是按照下一步能有的出路的个数升序排序，先搜少的. 什么意思，比如当前在A点，A的下一步有B和C两种跳法. 而我告诉你B的再下一步有6种跳法，而C的再下一步只有3种跳法. 那么你dfs的时候就要先搜C再搜B（而不能傻乎乎的逆时针逐一开拓）. 因为你不就只需要一个解嘛~ 我当然先搜出路少的. 因为一旦我找到了一个解就不玩了. 但是如果求全部解的话, 是无所谓先搜哪个的.

但是本题不是这样，本题是要求字典序最小的解. 所以不能按照再进一步出口的数量来排序, 而要字典序排序. 即优先搜列标号小的（因为棋盘的列就是字母） 其次是行标号小的. 所以我们就知道搜索的顺序并不是逆时针.

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
56
57
58
59
60
61
62
63
64
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int scenario, p,q, dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}}; // 这就是字典序最小的搜索顺序
bool v[30][30];
int ans_x[30], ans_y[30];

bool dfs(int i, int j, int step) // 当前决定ans_x[step]和ans_y[step], 当前位于i行,j列
{
	if (step==p*q) // 说明走完了
	{
		printf("Scenario #%d:\n", scenario);
		for (int i = 0; i<step; i++)
		{
			putchar('A'+ans_y[i]-1);
			printf("%d", ans_x[i]);
		}
		puts("");
		return true;
	}
	for (int t = 0,ni,nj; t<8; t++) //开辟下一步
	{
		ni = i+dir[t][0], nj = j+dir[t][1];
		if (ni>=1&&ni<=p&&nj>=1&&nj<=q&&!v[ni][nj])
		{
			v[ni][nj] = true, ans_x[step] = ni, ans_y[step] = nj;
			if (dfs(ni, nj, step+1))
			{
				return true;
			}
			v[ni][nj] = false; // 改回来
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	for(scenario = 1; scenario<=kase; scenario++)
	{
		if (scenario>1)
		{
			puts("");
		}
		scanf("%d%d", &p, &q);
		memset(v, 0, sizeof(v));
		v[1][1] = true;
		ans_x[0] = 1, ans_y[0] = 1;
		if (!dfs(1,1,1)) // 从第一行第一列(即A1)开始dfs
		{
			printf("Scenario #%d:\n", scenario);
			puts("impossible");
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 96kB
Length 1210
Lang C++
Submitted 2019-09-18 19:05:28
Shared
RemoteRunId 20872213