BFS算法

【道德经·第二十七章】 善行，无辙迹；善言，无瑕谪；善数，不用筹策；善闭，无关楗而不可开；善结，无绳约而不可解。是以圣人常善救人，故无弃人；常善救物，故无弃物。

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

int minDepth(TreeNode* root) {
    if(!root) return 0;

    queue<TreeNode*> q;
    q.push(root);

    int dep = 1;
    while(!q.empty()) {
        int sz = q.size();
        for(int i = 0; i < sz; i++) {
            TreeNode *t = q.front(); q.pop();
            if(!t->left && !t->right) return dep;
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }

        dep++;
    }

    return dep;
}

433. 最小基因变化

找出并返回能够使 start 变化为 end 所需的最少变化次数。

vector<char> gens{'A', 'C', 'G', 'T'};
int minMutation(string start, string end, vector<string>& bank) {
    if(bank.empty()) return -1;
    unordered_set<string> s{bank.begin(), bank.end()};
    unordered_set<string> visited;
    queue<string> q{{start}};
    int level = 0;
    while(!q.empty()) {
        for(int i = q.size(); i > 0; i--) {
            string t = q.front(); q.pop();
            if(t == end) return level;
            for(int j = 0; j < t.size(); j++) {
                char old = t[j];
                for(char c : gens) {
                    t[j] = c;
                    if(s.count(t) && !visited.count(t)) {
                        visited.insert(t);
                        q.push(t);
                    }
                }
                t[j] = old;
            }
        }
        
        ++level;
    }
    
    return -1;
}

752. 打开转盘锁

给出解锁需要的最小旋转次数。

string plusOne(string s, int j) {
    if(s[j] == '9') 
        s[j] = '0';
    else 
        s[j] += 1;
    
    return s;
}

string minusOne(string s, int j) {
    if(s[j] == '0')
        s[j] = '9';
    else 
        s[j] -= 1;

    return s;
}

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> dead, vis;
    for(string& s : deadends) dead.insert(s);

    queue<string> q;
    q.push("0000");
    
    vis.insert("0000");

    int step = 0;
    while(!q.empty()) {
        int sz = q.size(); 
        for(int i = 0; i < sz; i++) {
            string t = q.front(); q.pop();

            if(dead.count(t)) 
                continue;
            if(t == target) 
                return step;
            
            for(int j = 0; j < 4; j++) {
                string up = plusOne(t, j);
                if(!vis.count(up)) {
                    q.push(up);
                    vis.insert(up);
                }

                string down = minusOne(t, j);
                if(!vis.count(down)) {
                    q.push(down);
                    vis.insert(down);
                }
            }
        }

        step++;
    }

    return -1;
}

1293. 网格中的最短路径

找出从左上角到右下角的最短路径，并返回步数。

vector<vector<int> > dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size(), ans = 0;
    
    vector<vector<int> > vis(m, vector<int>(n, -1));
    
    vis[0][0] = k;
    queue<vector<int> > q;

    q.push({0, 0, k});
    while(!q.empty()) {
        for(int i = q.size(); i > 0; i--) {
            auto t = q.front(); q.pop();

            if(t[0]==m-1 && t[1]==n-1) return ans;

            for(auto dir : dirs) {
                int x = t[0]+dir[0], y = t[1]+dir[1];
                if(x<0 || x>=m || y<0 || y>=n) continue;

                int newK = t[2]-grid[x][y];
                if(newK<0 || newK<=vis[x][y]) continue;

                vis[x][y] = newK;
                q.push({x, y, newK});
            }
        }
        // 扩散了一层，路径增加一
        ++ans;
    }

    return -1;;
}

675. 为高尔夫比赛砍树

按照树的高度从低向高砍掉所有的树。

示例 1：

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

提示：

• m == forest.length
• n == forest[i].length
• 1 <= m, n <= 50
• 0 <= forest[i][j] <= 109

实现代码：

class Solution {
public:
    struct data{
        int w, x, y;
        data(int w, int x, int y){
            this->w = w;
            this->x = x;
            this->y = y;
        }
        data(){

        }
    };
    int n, m;
    int visited[55][55];
    int dir_x[4] = {0, 0, -1, 1};
    int dir_y[4] = {1, -1, 0, 0};
    int bfs(vector<vector<int>>& forest, int start_x, int start_y, int target_x, int target_y){
        int step = 0;
        queue<pair<int, int>> q;
        q.push({start_x, start_y});
        visited[start_x][start_y] = 1;
        while(!q.empty()){
            int q_size = q.size();
            for(int i = 0; i < q_size; i++){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if(x == target_x && y == target_y) return step;
                for(int j = 0; j < 4; j++){
                    int xx = x + dir_x[j];
                    int yy = y + dir_y[j];
                    if(xx >= 0 && yy >= 0 && xx < m && yy < n && forest[xx][yy] && !visited[xx][yy]){
                        q.push({xx, yy});
                        visited[xx][yy] = 1;
                    }
                }
            }
            step++;
        }   
        return -1;
    }
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        vector<data> arr;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(forest[i][j] > 1){
                    // 1是地面不是树
                    arr.push_back({forest[i][j], i, j});
                }
            }
        }
        auto cmp = [&](const data &a, const data &b){
            return a.w < b.w;//小到大
        };
        sort(arr.begin(), arr.end(), cmp);
        int pre_x = 0, pre_y = 0, ans = 0;
        for(auto [w, x, y] : arr){
            int step = bfs(forest, pre_x, pre_y, x, y);
            // cout << step << endl;
            if(step == -1) return -1;
            ans += step;
            memset(visited, 0, sizeof(visited));
            pre_x = x, pre_y = y;
        }
        return ans;
    }
};

位我上者，灿烂星空；道德律令，在我心中。