leetcode::shortest_path_to_get_all_keys::Solution类 参考

#include <leetcode.h>

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

详细描述

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

成员函数说明

shortestPathAllKeys()

int leetcode::shortest_path_to_get_all_keys::Solution::shortestPathAllKeys ( vector< string > &  grid )

static

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

                                                              {
            priority_queue<frame> pq;
            int m        = grid.size();
            int n        = grid[0].size();
            int start_x  = 0;
            int start_y  = 0;
            int lock_cnt = 0;
            unordered_map<unsigned, vector<vector<int>>> min_step;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == START) {
                        start_x = i;
                        start_y = j;
                    } else if(isupper(grid[i][j])) {
                        lock_cnt++;
                    }
                }
            }
            frame start(start_x, start_y, lock_cnt);
            pq.push(start);
            while(!pq.empty()) {
                frame f = pq.top();
                pq.pop();
                if(f.keys.size() == lock_cnt) {
                    return f.step;
                }
                if(!min_step.contains(f.get_mask())) {
                    min_step[f.get_mask()] = vector(m, vector(n, INT_MAX));
                }
                if(min_step[f.get_mask()][f.x][f.y] <= f.step) {
                    continue;
                }
                min_step[f.get_mask()][f.x][f.y] = f.step;
                const pair<int, int> nexts[4]    = {{f.x + 1, f.y}, {f.x - 1, f.y}, {f.x, f.y + 1}, {f.x, f.y - 1}};
                for(const auto &[n_x, n_y]: nexts) {
                    if(n_x >= 0 && n_x < m && n_y >= 0 && n_y < n && grid[n_x][n_y] != WALL) {
                        if(islower(grid[n_x][n_y])) {
                            frame next = f;
                            next.x     = n_x;
                            next.y     = n_y;
                            next.step++;
                            next.keys.insert(grid[n_x][n_y]);
                            if(!min_step.contains(next.get_mask())) {
                                min_step[next.get_mask()] = vector(m, vector(n, INT_MAX));
                            }
                            if(min_step[next.get_mask()][n_x][n_y] > next.step) {
                                pq.push(next);
                            }
                        } else if(isupper(grid[n_x][n_y])) {
                            if(f.keys.contains(static_cast<char>(tolower(grid[n_x][n_y])))) {
                                frame next = f;
                                next.x     = n_x;
                                next.y     = n_y;
                                next.step++;
                                if(!min_step.contains(next.get_mask())) {
                                    min_step[next.get_mask()] = vector(m, vector(n, INT_MAX));
                                }
                                if(min_step[next.get_mask()][n_x][n_y] > next.step) {
                                    pq.push(next);
                                }
                            }
                        } else {
                            frame next = f;
                            next.x     = n_x;
                            next.y     = n_y;
                            next.step++;
                            if(!min_step.contains(next.get_mask())) {
                                min_step[next.get_mask()] = vector(m, vector(n, INT_MAX));
                            }
                            if(min_step[next.get_mask()][n_x][n_y] > next.step) {
                                pq.push(next);
                            }
                        }
                    }
                }
            }
            return -1;
        }

引用了 leetcode::shortest_path_to_get_all_keys::frame::get_mask(), leetcode::shortest_path_to_get_all_keys::frame::keys, leetcode::shortest_path_to_get_all_keys::START, leetcode::shortest_path_to_get_all_keys::frame::step, leetcode::shortest_path_to_get_all_keys::WALL, leetcode::shortest_path_to_get_all_keys::frame::x , 以及 leetcode::shortest_path_to_get_all_keys::frame::y.

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

---

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

• leetcode.h
• leetcode.cpp