面试必刷算法TOP101之BFS篇 TOP10

腐烂的橘子

题目来源：Leetcode
1、问题描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。
  

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。

如果不可能，返回 -1 。

示例：

2、思路解析

3、代码实现

class Solution {
public:
    int net[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
    int orangesRotting(vector<vector<int>>& grid) {
        int row=grid.size();
        int col=grid[0].size();
        queue<pair<int,int>>v;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==2){
                    //入队
                    v.push(make_pair(i,j));
                }
            }
        }
        int minTime=0;
        while(!v.empty()){
            int flag=0;
            int size=v.size();
            //size是队列中所有的腐烂橘子的数量
            while(size--){
                //拿到腐烂橘子的坐标
                pair<int,int> ms=v.front();
                v.pop();
                //上下左右腐烂橘子
                for(int i=0;i<4;i++){
                    int x=ms.first+net[i][0];
                    int y=ms.second+net[i][1];
                    if(x<0||x>=row||y<0||y>=col){
                        continue;
                    }
                    //腐烂橘子
                    if(grid[x][y]==1){
                        flag=1;
                        grid[x][y]=2;
                        //腐烂橘子入队
                        v.push(make_pair(x,y));
                    }
                }
            }
            //
            if(flag){
            minTime++;
            }
        }
         for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
            return -1;
                }
            }
        }
        return minTime;
    }
};

单词接龙

题目来源：Leetcode
1、问题描述
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

• 每一对相邻的单词只差一个字母。
  

• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。
  

  注意， beginWord 不需要在 wordList 中。
  

• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。

如果不存在这样的转换序列，返回 0 。

示例：

2、思路解析

3、代码实现

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
                queue<string> v;
                //用来存放已经变h换过的单词
                unordered_set<string> oldStr;
                unordered_set<string> dict;
                for(auto it:wordList){
                    dict.insert(it);
                }
                //标志位存放已经使用的单词
                oldStr.insert(beginWord);
                v.push(beginWord);
                int step=1;
                while(!v.empty()){
                    //经过变换在字典中可以查到单词数量
                    int size=v.size();
                    while(size--){
                        string str=v.front();
                        v.pop();
                        if(str==endWord)
                            return step;
                        for(int i=0;i<str.size();i++){
                            string newStr=str;
                            for(char ch='a';ch<='z';ch++){
                                newStr[i]=ch;
                                //判断修改之后是否在字典中存在
                                if(dict.find(newStr)!=dict.end()&&oldStr.find(newStr)==oldStr.end()){
                                    //将存在的单词放到队列中
                                    //更新oldStr就是被查找过的单词
                                    v.push(newStr);
                                    oldStr.insert(newStr);
                                }
                            }

                        }
                   
                    }
                ++step;
                }
                return 0;
    }
};

打开转盘锁

题目来源：Leetcode
1、问题描述
你有一个带有四个圆形拨轮的转盘锁。

每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。

每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。

每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

2、思路和上一题基本差不多
3、代码实现

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q;
        unordered_set<string> v(deadends.begin(),deadends.end());
        if(v.find("0000")!=v.end()){
            return -1;
        }
        //用来存储使用过的字符串；
        unordered_set<string> oldStr;
        oldStr.insert("0000");
        q.push("0000");
        int step=0;
        while(!q.empty()){
            //结果变换开始使用的密码的数量
            int size=q.size();
            while(size--){
                string newStr=q.front();
                q.pop();
                if(newStr==target){
                    return step;
                }
         
                for(int i=0;i<newStr.size();i++){
                     string upStr=newStr;
                     string downStr=newStr;
                    //因为每次只能有一个转盘转一次，所以只能每次改变一个字符
                    //一个字符只能向下向上改变一次

                    //向上就是给第i个转盘向前转动一次如果是9下一个就是0，其他就+1就可以
                    upStr[i]=upStr[i]=='9'?'0':upStr[i]+1;
                    //向下就是给第i个转盘向后转动一次如果是0下一个就是9，其他就-1就可以
                    downStr[i]=downStr[i]=='0'?'9':downStr[i]-1;
                    //必要条件就是不在锁数组中，接着不能是使用过的
                    if(v.find(upStr)==v.end()&&oldStr.find(upStr)==oldStr.end()){
                        //可以使用的密码；
                        q.push(upStr);
                        oldStr.insert(upStr);
                    }
                      if(v.find(downStr)==v.end()&&oldStr.find(downStr)==oldStr.end()){
                        //可以使用的密码；
                        q.push(downStr);
                        oldStr.insert(downStr);
                    }
                }
            }
            step++;
        }
return -1;
    }
};