leetcode::minimum_cost_to_make_at_least_one_valid_path_in_a_grid::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static int	minCost (vector< vector< int > > &grid)

详细描述

在文件 leetcode.h 第 2940 行定义.

成员函数说明

minCost()

int leetcode::minimum_cost_to_make_at_least_one_valid_path_in_a_grid::Solution::minCost ( vector< vector< int > > &  grid )

static

在文件 leetcode.cpp 第 8142 行定义.

                                                       {
            const int m = grid.size();
            const int n = grid[0].size();
            vector g(m, vector<Node *>(n, nullptr));
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    g[i][j] = new Node(i, j);
                }
            }
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    pair<int, int> nexts[4] = {{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}};
                    for(auto [x, y]: nexts) {
                        if(x >= 0 && x < m && y >= 0 && y < n) {
                            g[i][j]->siblings.insert(make_pair(g[x][y], 1));
                        }
                    }
                    int x = i;
                    int y = j;
                    switch(grid[i][j]) {
                        case 1:
                            y++;
                            break;
                        case 2:
                            y--;
                            break;
                        case 3:
                            x++;
                            break;
                        case 4:
                            x--;
                            break;
                    }
                    if(x >= 0 && x < m && y >= 0 && y < n) {
                        g[i][j]->siblings[g[x][y]] = 0;
                    }
                }
            }
            priority_queue<pair<int, Node *>, vector<pair<int, Node *>>, mycmp> pq;
            unordered_set<Node *> vis;
            pq.push({0, g[0][0]});
            while(!pq.empty()) {
                auto [cost, node] = pq.top();
                pq.pop();
                if(vis.contains(node)) {
                    continue;
                }
                vis.insert(node);
                if(node->x == m - 1 && node->y == n - 1) {
                    return cost;
                }
                for(auto [sibling, c]: node->siblings) {
                    if(!vis.contains(sibling)) {
                        pq.push({cost + c, sibling});
                    }
                }
            }
            return 0;
        }

被这些函数引用 leetcode::minimum_cost_to_make_at_least_one_valid_path_in_a_grid::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp