算法leetcode

【搜索难题】力扣675-BFS常数优化,Astar,Hadlock算法

字数统计: 6.5k字   |   阅读时长: 35分
, ,
  • BFS 中的常数优化办法
    • 基本BFS
      1
      2
      中文版 TLE
      英文版 1712ms 勉强过
    • 优化1：将 forest[i][j] 值加进 Point 字段，而不在 cmp 中持有 forest 矩阵
      1
      2
      1944ms
      英文版 1628 ms
    • 优化2：将 Point 的 x, y 变成 pos (x * m + y)
      1
      2
      1760ms
      英文版 1392ms
    • 优化3：将 visited 的索引从 x, y 变成 pos (x * m + y)
      1
      2
      1396ms
      英文版 1132ms
    • 优化4：在 bfs 阶段用 Point.val 作为距离用，节点自带距离后省去 level_nodes
      1
      2
      1204ms
      英文版 1096ms
    • 优化5：将 forest 也变成 1 维
      1
      2
      1160ms
      英文版 960ms
    • 优化6：visited.assign 改成 memset(收益极高)
      1
      2
      640ms
      英文版 496ms
    • 优化7：快速 BFS (四周填充 0)
    • 优化8：方向枚举一维化
    • 优化9：手写队列

$1 题目

题目链接

675. 为高尔夫比赛砍树

题目描述

你被请来给一个要举办高尔夫比赛的树林砍树. 树林由一个非负的二维数组表示， 在这个数组中：

  • 0 表示障碍，无法触碰到.
  • 1 表示可以行走的地面.
  • 比 1 大的数 表示一颗允许走过的树的高度.

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你被要求按照树的高度从低向高砍掉所有的树，每砍过一颗树，树的高度变为 1 。

你将从（0，0）点开始工作，你应该返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

提示：

1
2
3
1 <= forest.length <= 50
1 <= forest[i].length <= 50
0 <= forest[i][j] <= 10^9

样例

示例 1:
输入:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
输出: 6

示例 2:
输入:
[
[1,2,3],
[0,0,0],
[7,6,5]
]
输出: -1

示例 3:
输入:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
输出: 6
解释: (0,0) 位置的树，你可以直接砍去，不用算步数

$2 题解

从 (0, 0) 开始，对于每棵树，按照高度顺序，计算我们到下一棵树的距离，并将该距离添加到答案中。

算法的核心是计算我们到下一棵树的距离这一步。BFS 和 Astar 是常规方法，

  • BFS
  • Astar
  • Hadlock

以上三种算法有相同的最坏时间复杂度，$O(M^{2}N^{2})$

算法1： BFS

普通 BFS，队列中是网格中的节点

1
2
3
4
5
struct Point
{
    int x, y;
    Point(int x, int y):x(x),y(y){}
};

状态转移条件：

1
2
3
4
5
6
对于状态 cur = q.front();
看 cur 周围的四个点，如果
1. 没出界
2. 没有入队过 (visited[cur] == false)
3. 不是障碍
则可以转移(入队)

单纯看这个算法很简单，但是一跑发现会超时，但是凭直觉时间复杂度应该很难低于 $O(M^{2}N^{2})$，因此需要探索各种常数优化的办法，而优化常数的思路和实现不是很简单的。

代码

1
2
中文版 TLE
英文版 1712ms 勉强过
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct Point
{
    int x, y;
    Point(int x, int y):x(x),y(y){}
};

struct Cmp
{
    vector<vector<int> > forest;
    Cmp(const vector<vector<int> >& forest):forest(forest){}
    bool operator()(const Point& point1, const Point& point2) const
    {
        return forest[point1.x][point1.y] < forest[point2.x][point2.y];
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp(forest);
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(cmp.forest[i][j] > 1)
                    trees.push_back(Point(i, j));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, 0), trees[i], cmp.forest, visited);
            else
                d = bfs(trees[i - 1], trees[i], cmp.forest, visited);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, Point p2, const vector<vector<int> >& forest, vector<vector<bool> >& visited)
    {
        if(p1.x == p2.x && p1.y == p2.y)
            return 0;
        int n = forest.size(), m = forest[0].size();
        queue<Point> q;
        visited.assign(n, vector<bool>(m, false));
        visited[p1.x][p1.y] = true;
        q.push(p1);
        vector<Point> level_nodes;
        int dist = 0;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            ++dist;
            for(Point p: level_nodes)
            {
                for(int d = 0; d < 4; ++d)
                {
                    int x = p.x + dx[d], y = p.y + dy[d];
                    if(x == p2.x && y == p2.y)
                        return dist;
                    if(x < 0 || x >= n || y < 0 || y >= m) continue;
                    if(visited[x][y]) continue;
                    if(forest[x][y] == 0) continue;
                    visited[x][y] = true;
                    q.push(Point(x, y));
                }
            }
        }
        return -1;
    }
};

优化：常数优化

  • 思路1 用自己的 struct 代替 vector<int> 作为 queue 内元素，queue 里套 vector<int> 效率很低
  • 思路2 将 2 维数组展开到1 维
  • 思路3 memset 代替重拷贝或重分配标记矩阵
  • 思路4 标记从出队时提前到入队时
  • 思路5 剪枝，提前结束遍历
  • 思路6 快速BFS，四周填充零
  • 思路7 方向枚举一维化
  • 思路8 手写队列

优化1：将 forest[i][j] 值加进 Point 字段，而不在 cmp 中持有 forest 矩阵

1
2
1944ms
英文版 1628 ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
struct Point
{
    int x, y, val;
    Point(int x, int y, int val):x(x),y(y),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(forest[i][j] > 1)
                    trees.push_back(Point(i, j, forest[i][j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, 0, forest[0][0]), trees[i], forest, visited);
            else
                d = bfs(trees[i - 1], trees[i], forest, visited);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, Point p2, const vector<vector<int> >& forest, vector<vector<bool> >& visited)
    {
        if(p1.x == p2.x && p1.y == p2.y)
            return 0;
        int n = forest.size(), m = forest[0].size();
        queue<Point> q;
        visited.assign(n, vector<bool>(m, false));
        visited[p1.x][p1.y] = true;
        q.push(p1);
        vector<Point> level_nodes;
        int dist = 0;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            ++dist;
            for(Point p: level_nodes)
            {
                for(int d = 0; d < 4; ++d)
                {
                    int x = p.x + dx[d], y = p.y + dy[d];
                    if(x == p2.x && y == p2.y)
                        return dist;
                    if(x < 0 || x >= n || y < 0 || y >= m) continue;
                    if(visited[x][y]) continue;
                    if(forest[x][y] == 0) continue;
                    visited[x][y] = true;
                    q.push(Point(x, y, forest[x][y]));
                }
            }
        }
        return -1;
    }
};

优化2：将 Point 的 x, y 变成 pos (x * m + y)

1
2
1760ms
英文版 1392ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, forest[i][j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, forest[0][0]), trees[i], forest, visited);
            else
                d = bfs(trees[i - 1], trees[i], forest, visited);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, Point p2, const vector<vector<int> >& forest, vector<vector<bool> >& visited)
    {
        if(p1.pos == p2.pos)
            return 0;
        int n = forest.size(), m = forest[0].size();
        queue<Point> q;
        visited.assign(n, vector<bool>(m, false));
        visited[p1.pos / m][p1.pos % m] = true;
        q.push(p1);
        vector<Point> level_nodes;
        int dist = 0;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            ++dist;
            for(Point p: level_nodes)
            {
                for(int d = 0; d < 4; ++d)
                {
                    int i = p.pos / m, j = p.pos % m;
                    int x = i + dx[d], y = j + dy[d];
                    int pos = x * m + y;
                    if(x < 0 || x >= n || y < 0 || y >= m) continue;
                    if(visited[x][y]) continue;
                    if(forest[x][y] == 0) continue;
                    if(pos == p2.pos) // 改成一维后，只能放在这里，不能放在前面
                        return dist;
                    visited[x][y] = true;
                    q.push(Point(pos, forest[x][y]));
                }
            }
        }
        return -1;
    }
};

优化3：将 visited 的索引从 x, y 变成 pos (x * m + y)

1
2
1396ms
英文版 1132ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, forest[i][j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<bool> visited(n* m, false);
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, forest[0][0]), trees[i], forest, visited);
            else
                d = bfs(trees[i - 1], trees[i], forest, visited);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, Point p2, const vector<vector<int> >& forest, vector<bool>& visited)
    {
        if(p1.pos == p2.pos)
            return 0;
        int n = forest.size(), m = forest[0].size();
        queue<Point> q;
        visited.assign(n * m, false);
        visited[p1.pos] = true;
        q.push(p1);
        vector<Point> level_nodes;
        int dist = 0;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            ++dist;
            for(Point p: level_nodes)
            {
                for(int d = 0; d < 4; ++d)
                {
                    int i = p.pos / m, j = p.pos % m;
                    int x = i + dx[d], y = j + dy[d];
                    int pos = x * m + y;
                    if(x < 0 || x >= n || y < 0 || y >= m) continue;
                    if(visited[pos]) continue;
                    if(forest[x][y] == 0) continue;
                    if(pos == p2.pos) // 改成一维后，只能放在这里，不能放在前面
                        return dist;
                    visited[pos] = true;
                    q.push(Point(pos, forest[x][y]));
                }
            }
        }
        return -1;
    }
};

优化4：在 bfs 阶段用 Point.val 作为距离用，节点自带距离后省去 level_nodes

1
2
1204ms
英文版 1096ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, forest[i][j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<bool> visited(n* m, false);
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, 0), trees[i].pos, forest, visited);
            else
                d = bfs(Point(trees[i - 1].pos, 0), trees[i].pos, forest, visited);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, int p2_pos, const vector<vector<int> >& forest, vector<bool>& visited)
    {
        if(p1.pos == p2_pos)
            return 0;
        int n = forest.size(), m = forest[0].size();
        queue<Point> q;
        visited.assign(n * m, false);
        visited[p1.pos] = true;
        q.push(p1);
        while(!q.empty())
        {
            Point p = q.front();
            q.pop();
            for(int d = 0; d < 4; ++d)
            {
                int i = p.pos / m, j = p.pos % m;
                int x = i + dx[d], y = j + dy[d];
                int pos = x * m + y;
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(visited[pos]) continue;
                if(forest[x][y] == 0) continue;
                if(pos == p2_pos) // 改成一维后，只能放在这里，不能放在前面
                    return p.val + 1;
                visited[pos] = true;
                q.push(Point(pos, p.val + 1));
            }
        }
        return -1;
    }
};

优化5：将 forest 也变成 1 维

1
2
1160ms
英文版 960ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        vector<int> spread(m * n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                spread[i * m + j] = forest[i][j];
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, spread[i * m + j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        vector<bool> visited(n* m, false);
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, 0), trees[i].pos, spread, visited, m);
            else
                d = bfs(Point(trees[i - 1].pos, 0), trees[i].pos, spread, visited, m);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, int p2_pos, const vector<int>& forest, vector<bool>& visited, int m)
    {
        if(p1.pos == p2_pos)
            return 0;
        int n = forest.size() / m;
        queue<Point> q;
        visited.assign(n * m, false);
        visited[p1.pos] = true;
        q.push(p1);
        while(!q.empty())
        {
            Point p = q.front();
            q.pop();
            for(int d = 0; d < 4; ++d)
            {
                int i = p.pos / m, j = p.pos % m;
                int x = i + dx[d], y = j + dy[d];
                int pos = x * m + y;
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(visited[pos]) continue;
                if(forest[pos] == 0) continue;
                if(pos == p2_pos) // 改成一维后，只能放在这里，不能放在前面
                    return p.val + 1;
                visited[pos] = true;
                q.push(Point(pos, p.val + 1));
            }
        }
        return -1;
    }
};

优化6：visited.assign 改成 memset(收益极高)

1
2
3
4
5
6
7
vector<bool> visited;
bfs(..., visited, ...);

int bfs(..., vector<bool>& visited, ...)
{
    visited.assign(...);
}

改成 

1
2
3
4
5
6
7
bool *visited = new bool[n * m]; // 动态数组只能开在堆上，因为 m, n 编译时不确定
bfs(..., visited, ...);

int bfs(..., bool* visited, ...)
{
    memset(visited, ...);
}
1
2
640ms
英文版 496ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        vector<int> spread(m * n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                spread[i * m + j] = forest[i][j];
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, spread[i * m + j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        bool *visited = new bool[n * m]; // 动态数组只能开在堆上，因为 m, n 编译时不确定
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
                d = bfs(Point(0, 0), trees[i].pos, spread, visited, m);
            else
                d = bfs(Point(trees[i - 1].pos, 0), trees[i].pos, spread, visited, m);
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int bfs(Point p1, int p2_pos, const vector<int>& forest, bool* visited, int m)
    {
        if(p1.pos == p2_pos)
            return 0;
        int n = forest.size() / m;
        queue<Point> q;
        memset(visited, false, sizeof(bool) * n * m);
        visited[p1.pos] = true;
        q.push(p1);
        while(!q.empty())
        {
            Point p = q.front();
            q.pop();
            for(int d = 0; d < 4; ++d)
            {
                int i = p.pos / m, j = p.pos % m;
                int x = i + dx[d], y = j + dy[d];
                int pos = x * m + y;
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(visited[pos]) continue;
                if(forest[pos] == 0) continue;
                if(pos == p2_pos) // 改成一维后，只能放在这里，不能放在前面
                    return p.val + 1;
                visited[pos] = true;
                q.push(Point(pos, p.val + 1));
            }
        }
        return -1;
    }
};

优化7：快速 BFS (四周填充零)

枚举方向 d，计算 x, y, pos

1
2
3
int i = p.pos / m, j = p.pos % m;
int x = i + dx[d], y = j + dy[d];
int pos = x * m + y;

之后有 6 个判断

1
2
3
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(visited[pos]) continue;
if(forest[pos] == 0) continue;

如果在地图的外围加上一圈 ‘0’:

1
2
3
4
5
0 0 0 0 0
0|1 2 3|0
0|0 0 4|0
0|7 6 5|0
0 0 0 0 0

那么就可以简化判断，两个判断就可以了

1
if(forest[x][y] && !vis[x][y])

优化8：方向枚举一维化

1
2
3
4
5
6
7
8
9
10
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

for(int d = 0; d < 4; ++d)
{
    int i = p.pos / m, j = p.pos % m;
    int x = i + dx[d], y = j + dy[d];
    int pos = x * m + y;
    ...
}

改成

1
2
3
4
5
6
7
8
9
10
int d[4] = {1, -1, m, -m}; // m 为矩阵的列数
for(int i = 0; i < 4; ++i) 
{
    int nxt = cur + d[i];
    if(forest[nxt] && !vis[nxt]) 
    { 
        // forest 和 vis 都是一维化之后的数组
        ...
    }
}

优化9：手写队列

1
2
3
4
5
6
7
8
9
10
int q[1000], r = 0 /* 读指针 */, w = 0 /* 写指针 */;

// 读操作
int val = q[r++];

// 写操作
q[w++] = val;

// 是否为空
bool empty = (r == w);

$3 扩展:

1. Astar

Astar 算法是另一种路径查找算法，其思想参考 Astar。

对于每个状态，增加 f, g, h 三个字段。

1
2
3
4
5
6
7
8
9
10
11
struct Point
{
    int x, y, val;
    Point(int x, int y, int val):x(x),y(y),val(val){}
};

struct AstarPoint: public Point
{
    int f, g, h;
    AstarPoint(int x, int y, int val, int f, int g, int h):Point(x, y, val),f(f),g(g),h(h){}
};

对于状态 node，node.f = node.g + node.h，其中：

  • node.g 是从 start 到 node 的实际距离。
  • node.h 是从 node 到 target 的距离的启发式。

优先级队列中，对状态的排序按照 f 从小到大排序

1
2
3
4
5
6
7
struct AstarCmp
{
    bool operator()(const AstarPoint& point1, const AstarPoint& point2) const
    {
        return point1.f < point2.f;
    }
}

估价函数： node.h = abs(node.x - target.x) + abs(node.y - target.y);

代码

主体代码在优化6 的基础上增加优化8。

Astar 由于涉及维护堆的操作，性能并不优秀。

1
1600ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
struct Tree
{
    int pos, val;
    Tree(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Tree& point1, const Tree& point2) const
    {
        return point1.val < point2.val;
    }
};

struct AstarPoint
{
    int pos;
    int g;
    int f, h;
    AstarPoint(int pos, int g, int h=-1):pos(pos),g(g),h(h)
    {
        f = g + h;
    }
};

struct AstarCmp
{
    bool operator()(const AstarPoint& point1, const AstarPoint& point2) const
    {
        return point1.f > point2.f;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Tree> trees;
        vector<int> spread(m * n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                spread[i * m + j] = forest[i][j];
                if(forest[i][j] > 1)
                    trees.push_back(Tree(i * m + j, spread[i * m + j]));
            }
        sort(trees.begin(), trees.end(), cmp);

        int ntree = trees.size();
        int result = 0;
        bool *visited = new bool[n * m]; // 动态数组只能开在堆上，因为 m, n 编译时不确定
        for(int i = 0; i < ntree; ++i)
        {
            int d;
            if(i == 0)
            {
                AstarPoint s(0, 0, h(0, trees[i].pos, m));
                d = bfs(s, trees[i].pos, spread, visited, m);
            }
            else
            {
                AstarPoint s(trees[i - 1].pos, 0, h(trees[i - 1].pos, trees[i].pos, m));
                d = bfs(s, trees[i].pos, spread, visited, m);
            }
            if(d == -1)
                return -1;
            result += d;
        }
        return result;
    }

private:
    int bfs(AstarPoint p1, int p2_pos, const vector<int>& forest, bool* visited, int m)
    {
        if(p1.pos == p2_pos)
            return 0;
        int N = forest.size();
        priority_queue<AstarPoint, vector<AstarPoint>, AstarCmp> pq;
        memset(visited, false, sizeof(bool) * N);
        visited[p1.pos] = true;
        pq.push(p1);
        int d[4] = {1, -1, m, -m}; // m 为矩阵的列数
        while(!pq.empty())
        {
            AstarPoint p = pq.top();
            pq.pop();
            if(p.pos == p2_pos) // 改成一维后，只能放在这里，不能放在前面
                return p.g;
            visited[p.pos] = true;
            int py = p.pos % m;
            for(int i = 0; i < 4; ++i)
            {
                if(py == 0 && i == 1) continue;
                if(py == m - 1 && i == 0) continue;
                int pos = p.pos + d[i];
                if(pos < 0 || pos >= N) continue;
                if(visited[pos]) continue;
                if(forest[pos] == 0) continue;
                AstarPoint nxt(pos, p.g + 1, h(pos, p2_pos, m));
                pq.push(nxt);
            }
        }
        return -1;
    }

    int h(int pos, int t, int m)
    {
        int h = abs(pos / m - t / m);
        int w = abs(pos % m - t % m);
        return w + h;
    }
};

2. HadLock 算法

HadLock 提出的 grid 上的最短路径算法，类似与 Astar.

参考：
Python-solution-based-on-wufangjie’s-(Hadlock’s-algorithm)
中文版官解

没有任何障碍物，从 source = (sr, sc) 到 target = (tr, tc) 的距离就是 taxi(source, target) = abs(sr-tr) + abs(sc-tc)。这表示必须行驶的最小距离。每当我们离开目标时，我们都会将这个最小值增加2，因为我们一步一个移动，再加上 taxicab 离我们新位置的距离增加了 1。

我们称 detour 为一次绕开目标的移动，可以证明，从源到目标的距离仅为 taxi(source, target) + 2 * detours，其中，从 source 到 target 的任何路径中，detours 的数量最小。

算法：

对于一个 source 和 target，称一个方格的迂回数为从 source 到该方格的任何路径中可能出现的最小迂回数。（这里，迂回道是针对 target 定义的——距离目标的步数。）
我们将按照 detour 编号的顺序执行优先级优先搜索。如果找到目标，则找到最低的 detour ，因此相应距离最低。同时使用 processed 跟踪节点，防止节点被访问两次。
由于每个相邻节点只能有相同的 detour 编号或更高的 detour 编号，因此一次最多只能考虑两个优先级。因此，我们可以使用 deque（双端队列）来执行此实现。我们将首先放置具有相同要展开的 detour 编号的节点，在完成所有具有当前编号的节点之后，将展开具有更高迂回道编号的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
Just my own very similar implementation of @wufangjie's solution (and some terminology from the Hadlock algorithm which @awice mentioned to me), with some more explanation. Gets accepted in about 700 ms.

Basically find the trees, sort them by order, find the distance from each tree to the next, and sum those distances. But how to find the distance from one cell to some other cell? BFS is far to slow for the current test suite. Instead use what's apparently known as "Hadlock's Algorithm" (though I've only seen high-level descriptions of that). First try paths with no detour (only try steps in the direction towards the goal), then if necessary try paths with one detour step, then paths with two detour steps, etc. The distance then is the Manhattan distance plus twice the number of detour steps (twice because you'll have to make up for a detour step with a later step back towards the goal).

How to implement that?

Round 1: Run a DFS only on cells that you can reach from the start cell with no detour towards the goal, i.e., only walking in the direction towards the goal. If this reaches the goal, we're done. Otherwise...
Round 2: Try again, but this time try starting from all those cells reachable with one detour step. Collect these in round 1.
Round 3: If round 2 fails, try again but start from all those cells reachable with two detour steps. Collect these in round 2.
And so on...
If there are no obstacles, then this directly walks a shortest path towards the goal, which is of course very fast. Much better than BFS which would waste time looking in all directions. With only a few obstacles, it's still close to optimal.

My distance function does this searching algorithm. I keep the current to-be-searched cells in my now stack. When I move to a neighbor that's closer to the goal, I also put it in now. If it's not closer, then that's a detour step so I just remember it on my soon stack for the next round.
1
2
900ms
英文版 700ms
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
struct Point
{
    int pos, val;
    Point(int pos, int val):pos(pos),val(val){}
};

struct Cmp
{
    bool operator()(const Point& point1, const Point& point2) const
    {
        return point1.val < point2.val;
    }
};

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;
        int n = forest.size(), m = forest[0].size();
        Cmp cmp;
        vector<Point> trees;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(forest[i][j] > 1)
                    trees.push_back(Point(i * m + j, forest[i][j]));
            }
        sort(trees.begin(), trees.end(), cmp); // O(MNlog(MN))

        // 是否所有的树都能走到 O(MN)
        // 记录所有能走到的点(一维形式) O(MN)
        unordered_set<int> reached;
        bfs(forest, reached);
        for(auto tree: trees)
            if(reached.find(tree.pos) == reached.end())
                return -1;

        // 所有树都走得到，结果一定不为 -1
        int result = 0;
        int prev = 0;
        vector<bool> visited, used;
        for(auto tree: trees)
        {
            visited.assign(m * n, false);
            used.assign(m * n, false);
            int d = dfs(prev, tree.pos, forest, visited, used);
            result += d;
            prev = tree.pos;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1}; // 右，左，下，上
    int dy[4] = {1, -1, 0, 0};
    using PII = pair<int, int>;

    int dfs(int pos1, const int pos, const vector<vector<int> >& forest, vector<bool>& visited, vector<bool>& used)
    {
        if(pos1 == pos) return 0;
        int n = forest.size(), m = forest[0].size();
        int x = pos / m, y = pos % m;

        int result = manhattan(pos1 / m, pos1 % m, x, y);
        // st2 始终比 st1 多一个 detours
        // 因为当前点始终从 st1 取，下一个新点如果要 detour，先放进 st2，不需要 detour 才直接进 st1
        // st1 空了才会把 st2 倒进 st1
        vector<int> st1, st2;
        st1.push_back(pos1);
        used[pos1] = true; // 已经见过的点
        visited[pos1] = true; // 已经使用的点
        int detours = 0;

        while(true)
        {
            if(st1.empty())
            {
                // 不增加 detours 到不了终点
                swap(st1, st2);
                for(int pos1: st1) used[pos1] = true;
                ++detours;
            }

            int pos1 = st1.back();
            st1.pop_back();
            if(pos1 == pos)
                break;

            int x1 = pos1 / m, y1 = pos1 % m;
            // 与目标方向一致的下一点进 st1, 与目标方向不一致的下一点进 st2
            // 新点若与目标方向一致则加入 visited 和 used，直接进入 st1
            // 新点若与目标方向不一致则只加入 visited，先加入 st2 暂存
            for(int d: positive_direction(x1, y1, x, y))
            {
                // (x1, y1) 朝着 (x, y) 的方向
                int x2 = x1 + dx[d], y2 = y1 + dy[d];
                if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) continue;
                if(forest[x2][y2] == 0) continue;
                int pos2 = x2 * m + y2;
                if(used[pos2]) continue;
                visited[pos2] = true;
                used[pos2] = true;
                st1.push_back(pos2);
            }
            for(int d: negative_direction(x1, y1, x, y))
            {
                // (x1, y1) 朝着 (x, y) 相反的方向
                int x2 = x1 + dx[d], y2 = y1 + dy[d];
                if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) continue;
                if(forest[x2][y2] == 0) continue;
                int pos2 = x2 * m + y2;
                if(visited[pos2]) continue;
                visited[pos2] = true;
                st2.push_back(pos2);
            }
        }

        return result + detours * 2;
    }

    vector<int> positive_direction(int x1, int y1, int x, int y)
    {
        // (x1, y1) 朝着 (x, y) 的方向
        vector<int> result;
        if(x1 > x) result.push_back(3); // 上
        if(x1 < x) result.push_back(2); // 下
        if(y1 > y) result.push_back(1); // 左
        if(y1 < y) result.push_back(0); // 右
        return result;
    }

    vector<int> negative_direction(int x1, int y1, int x, int y)
    {
        // (x1, y1) 朝着 (x, y) 相反的方向
        vector<int> result;
        if(x1 >= x) result.push_back(2); // 上
        if(x1 <= x) result.push_back(3); // 下
        if(y1 >= y) result.push_back(0); // 左
        if(y1 <= y) result.push_back(1); // 右
        return result;
    }

    void bfs(const vector<vector<int> >& forest, unordered_set<int>& reached)
    {
        int n = forest.size(), m = forest[0].size();
        vector<int> visited(m * n, false);
        visited[0] = true;
        queue<int> q;
        q.push(0);
        while(!q.empty())
        {
            int p = q.front();
            q.pop();
            reached.insert(p);
            for(int d = 0; d < 4; ++d)
            {
                int x = p / m + dx[d], y = (p % m) + dy[d];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(forest[x][y] == 0) continue;
                int pos = x * m + y;
                if(visited[pos]) continue;
                visited[pos] = true;
                q.push(pos);
            }
        }
    }

    int manhattan(int x1, int y1, int x2, int y2)
    {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};
Share