算法leetcode

力扣1091-Astar,IDAstar

字数统计: 1.4k字   |   阅读时长: 7分
, ,

本题我们看一个

  • 常规BFS, 无权图最短路模型, Ref BFS
  • Astar, Ref Astar
  • IDAstar, Ref IDAstar
  • c++ 二维动态数组的创建和初始化

$1 题目

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

  • 路径途经的所有单元格都的值都是 0 。
  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

提示：

1
2
3
4
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 为 0 或 1

示例 1：
输入：grid = [[0,1],[1,0]]
输出：2

示例 2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

示例 3：
输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

$2 题解

算法1: 基础BFS

代码 (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
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();
        if(N == 1 && grid[0][0] == 0) return 1;
        if(N == 1 && grid[0][0] == 1) return -1;
        if(grid[0][0] == 1) return -1;

        vector<vector<bool> > visited(N, vector<bool>(N, false));
        queue<PII> q;
        q.push(PII(0, 0));
        visited[0][0] = true;
        int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
        int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

        vector<PII> level_nodes;
        int result = 0;
        bool get_end = false;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            for(PII point: level_nodes)
            {
                if(point.first == N - 1 && point.second == N - 1)
                {
                    get_end = true;
                    break;
                }
                for(int d = 0; d < 8; ++d)
                {
                    PII nxt(point.first + dx[d], point.second + dy[d]);
                    if(_check(nxt, grid, visited))
                    {
                        q.push(nxt);
                        visited[nxt.first][nxt.second] = true;
                    }
                }
            }
            ++result;
            if(get_end)
                return result;
        }
        return -1;
    }

private:
    using PII = pair<int, int>;

    bool _check(const PII& nxt, const vector<vector<int> >& grid, vector<vector<bool> >& visited)
    {
        int N = grid.size();
        if(nxt.first < 0 || nxt.first >= N || nxt.second < 0 || nxt.second >= N) return false;
        return (!visited[nxt.first][nxt.second]) && (grid[nxt.first][nxt.second] == 0);
    }
};

算法2： Astar

状态设计

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

优先级队列中的比较准则

1
2
3
4
5
6
7
struct Cmp
{
    bool operator()(const State& s1, const State& s2) const
    {
        return s1.d + s1.h > s2.d + s2.h;
    }
};

因为可以斜着走，估价函数不能取 h = abs(x - tx) + abs(y - ty)

1
2
3
4
int h(int x, int y, int tx, int ty)
{
    return max(abs(tx - x), abs(y - ty));
}

代码

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

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

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();
        if(N == 1 && grid[0][0] == 0) return 1;
        if(N == 1 && grid[0][0] == 1) return -1;
        if(grid[0][0] == 1) return -1;
        // N * N
        State s(0, 0, 1, h(0, 0, N - 1, N - 1));
        return bfs(grid, s, N - 1, N - 1);
    }

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

    int bfs(const vector<vector<int>>& grid, State s, int tx, int ty)
    {
        priority_queue<State, vector<State>, Cmp> pq;
        pq.push(s);
        int N = grid.size();
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        while(!pq.empty())
        {
            State cur = pq.top();
            pq.pop();
            if(cur.x == tx && cur.y == ty)
                return cur.d;
            if(visited[cur.x][cur.y])
                continue;
            visited[cur.x][cur.y] = true;
            for(int d = 0; d < 8; ++d)
            {
                int x = cur.x + dx[d];
                int y = cur.y + dy[d];
                if(x < 0 || x >= N || y < 0 || y >= N)
                    continue;
                if(grid[x][y] != 0)
                    continue;
                if(visited[x][y])
                    continue;
                State nxt(x, y, cur.d + 1, h(x, y, tx, ty));
                pq.push(nxt);
            }
        }
        return -1;
    }

    int h(int x, int y, int tx, int ty)
    {
        return max(abs(tx - x), abs(y - ty));
    }
};

算法3：IDAstar

c++ 二维动态数组的创建和初始化

1
2
3
4
5
bool **visited = new bool*[N];
for(int i = 0; i < N; ++i)
    visited[i] = new bool[M];
for(int i = 0; i < N; ++i)
    memset(visited[i], false, M * sizeof(bool));

代码

超时了

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
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();
        if(N == 1 && grid[0][0] == 0) return 1;
        if(N == 1 && grid[0][0] == 1) return -1;
        if(grid[0][0] == 1) return -1;
        bool **visited = new bool*[N];
        for(int i = 0; i < N; ++i)
            visited[i] = new bool[N];
        for(int i = 0; i < N; ++i)
            memset(visited[i], false, N * sizeof(bool));

        int max_depth = N * N;
        int depth = 1;
        while(depth <= max_depth && !dfs(grid, 0, 0, N - 1, N - 1, 1, depth, visited))
        {
            for(int i = 0; i < N; ++i)
                memset(visited[i], false, N * sizeof(bool));
            ++depth;
            visited[0][0] = true;
        }
        if(depth > max_depth)
            return -1;
        return depth;
    }

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

    bool dfs(const vector<vector<int>>& grid, int i, int j, int tx, int ty, int depth, const int max_depth, bool** visited)
    {
        if(depth + h(i, j, tx, ty) > max_depth)
            return false;
        if(i == tx && j == ty)
            return true;
        int N = grid.size();
        for(int d = 0; d < 8; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= N || y < 0 || y >= N)
                continue;
            if(grid[x][y] != 0)
                continue;
            if(visited[x][y])
                continue;
            visited[x][y] = true;
            if(dfs(grid, x, y, tx, ty, depth + 1, max_depth, visited))
                return true;
            visited[x][y] = false;
        }
        return false;
    }

    int h(int x, int y, int tx, int ty)
    {
        return max(abs(tx - x), abs(y - ty));
    }
};
Share