【搜索难题】力扣1197-进击的骑士

  |  

摘要: 启发式搜索、记忆化搜索两套方法。自定义备忘录中状态的哈希函数。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文看一个搜索题,用 DFS 和 BFS 两套方法都可以解决。

如果用 DFS,需要引入记忆化搜索,并且由于状态的取值很稀疏,需要用哈希表维护备忘录,而这里的状态还需要自定义哈希函数。

如果用 BFS,也需要携带状态,之后可以设计估价函数用 AStar。


$1 题目

1197. 进击的骑士

一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上,你的 骑士 驻扎在坐标为 [0, 0] 的方格里。

骑士的走法和中国象棋中的马相似,走 “日” 字:即先向左(或右)走 1 格,再向上(或下)走 2 格;或先向左(或右)走 2 格,再向上(或下)走 1 格。

每次移动,他都可以按图示八个方向之一前进。

现在,骑士需要前去征服坐标为 [x, y] 的部落,请你为他规划路线。

最后返回所需的最小移动次数即可。本题确保答案是一定存在的。

提示:

1
|x| + |y| <= 300

示例 1:
输入:x = 2, y = 1
输出:1
解释:[0, 0] → [2, 1]

示例 2:
输入:x = 5, y = 5
输出:4
解释:[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

$2 题解

算法1: BFS

状态设计

1
2
3
4
5
6
7
struct State
{
int x;
int y;
int d;
State(int x, int y, int d):x(x),y(y),d(d){}
};

维护已经访问过的状态

x 和 y 的范围为[-300, 300],因此设定一个 OFFSET 将 x 和 y 的所有可能取值修正为正数,然后按最大范围开出 vector<vector<bool>>

代码 (C++)

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
struct State
{
int x;
int y;
int d;
State(int x, int y, int d):x(x),y(y),d(d){}
};

const int OFFSET = 305;

class Solution {
public:
int minKnightMoves(int x, int y) {
if(x == 0 && y == 0)
return 0;
queue<State> q;
q.push(State(0, 0, 0));
visited.assign(610, vector<bool>(610, false));
while(!q.empty())
{
State cur = q.front();
q.pop();
for(int d = 0; d < 8; ++d)
{
int i = cur.x + dx[d], j = cur.y + dy[d];
State nxt(i, j, cur.d + 1);
if(visited[nxt.x + OFFSET][nxt.y + OFFSET])
continue;
if(i == x && j == y)
return cur.d + 1;
visited[nxt.x + OFFSET][nxt.y + OFFSET] = true;
q.push(nxt);
}
}
return -1;
}

private:
vector<vector<bool>> visited;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
};

算法2: Astar

估价函数

马一次跳动可以走 3 长度,因此点 (x, y) 的估价函数设为该点到 (x0, y0) 的曼哈顿距离除以 3。

1
2
3
4
int h(int x, int y, int x0, int y0)
{
return (abs(x - x0) + abs(y - y0)) / 3;
}

代码 (C++)

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
int h(int x, int y, int x0, int y0)
{
return (abs(x - x0) + abs(y - y0)) / 3;
}

struct State
{
int x;
int y;
int d;
int h;
State(int x, int y, int d):x(x),y(y),d(d),h(0){}
bool operator==(const State& s) const
{
return this -> x == s.x && this -> y == s.y;
}
};

struct HeapCmp
{
bool operator()(const State& s1, const State& s2) const
{
return s1.d + s1.h > s2.d + s2.h;
}
};

const int OFFSET = 305;

class Solution {
public:
int minKnightMoves(int x, int y) {
State s(0, 0, 0);
s.h = h(0, 0, x, y);
priority_queue<State, vector<State>, HeapCmp> pq;
pq.push(s);
visited.assign(610, vector<bool>(610, false));
while(!pq.empty())
{
State cur = pq.top();
pq.pop();
if(cur.x == x && cur.y == y)
return cur.d;
if(visited[cur.x + OFFSET][cur.y + OFFSET])
continue;
visited[cur.x + OFFSET][cur.y + OFFSET] = true;
for(int d = 0; d < 8; ++d)
{
int i = cur.x + dx[d], j = cur.y + dy[d];
State nxt(i, j, cur.d + 1);
nxt.h = h(i, j, x, y);
if(visited[nxt.x + OFFSET][nxt.y + OFFSET])
continue;
pq.push(nxt);
}
}
return -1;
}

private:
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
vector<vector<bool>> visited;
};

算法3: 记忆化搜索

定义 solve(x, y, x0, y0) 表示 (x, y) 到 (x0, y0) 所需的步数。

如果将查找方向改为从 (x, y) 向 (0, 0) 走则可以改为 solve(x, y),x, y 始终 >= 0,如果小于零可以去相反数后调用。

由于从 (x, y) 寻找下一步的位置时,只考虑 x, y 两维均更接近 0 的方向。即 (x - 1, y - 2), (x - 2, y - 1)

代码 (C++)

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
struct State
{
int x;
int y;
State(int x, int y):x(x),y(y){}
bool operator==(const State& s) const
{
return this -> x == s.x && this -> y == s.y;
}
bool operator<(const State& s) const
{
return (this -> x + this -> y) < (s.y + s.x);
}
};

struct MyHash
{
static constexpr int OFFSET = 305;
int operator()(const State& s) const
{
return ((s.x + 305) * 305) + (s.y + 305);
}
};

class Solution {
public:
int minKnightMoves(int x, int y) {
return solve(abs(x), abs(y));
}

private:
unordered_map<State, int, MyHash> dp;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

int solve(int x, int y)
{
if(x == 0 && y == 0)
return 0;
if(x + y == 2)
return 2;
State s(x, y);
if(dp.count(s) > 0)
return dp[s];
return dp[s] = 1 + min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1)));
}
};

Share