C++回溯算法广度优先搜索举例分析

namespace BFS {
	struct pair {
		int _x;
		int _y;

		pair(int x, int y)
			:_x(x)
			, _y(y)
		{}
	};

	bool mapBFS(vector<vector<int>> mat, int sx, int sy, int ex, int ey)
	{
		int row = mat.size();
		int col = mat[0].size();

		queue<pair> q;
		q.push(pair(sx, sy));
		vector<vector<int>> book(row, vector<int>(col, 0));
		book[sx][sy] = 1;

		int nextP[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

		while (!q.empty())
		{
			pair curPos = q.front();
			q.pop();
			if (curPos._x == ex && curPos._y == ey)
				return true;
			//一个点的所有可能延伸的点
			for (int i = 0; i < 4; i++)
			{
				int curX = curPos._x + nextP[i][0];
				int curY = curPos._y + nextP[i][1];

				if (curX < 0 || curX >= row || curY < 0 || curY >= col)
					continue;
				//没有走过且不是障碍物
				if (mat[curX][curY] == 0 && book[curX][curY] == 0)
				{
					book[curX][curY] = 1;
					//保存新的位置
					q.push(pair(curX, curY));
				}
			}
		}

		return false;
	}
}

int main()
{
	vector<vector<int>> mat{ {0, 0, 1, 0},
							 {1, 0, 0, 1},
							 {0, 0, 0, 0},
							 {1, 1, 0, 0} };
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	cout << BFS::mapBFS(mat, sx, sy, ex, ey);

	return 0;
}

class Solution {
public:
    vector<vector<int>> levelOrder(node* root) {
        vector<vector<int>> result;
        if(!root)
            return result;
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
            //获取队列中的元素个数
            int sz = q.size();
            vector<int> rowV;
            while(sz--)
            {
                //保存当前元素在同一行
                Node* node = q.front();
                q.pop();
                rowV.push_back(node->val);
                //当前元素的孩子结点入队
                for(auto e : node->children)
                {
                    q.push(e);
                }
            }
            result.push_back(rowV);
        }

        return result;
    }
};

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int step = 0;
        int row = grid.size();
        int col = grid[0].size();
        queue<pair<int, int>> q;
        //把所有腐烂的橘子入队
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 2)
                    q.push(make_pair(i, j));
            }
        }

        static int nextP[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0 ,1}};
        while(!q.empty()){
            int sz = q.size();
            bool flag = false;
            while(sz--){
                pair curPos = q.front();
                q.pop();
                for(int i = 0; i < 4; i++){
                    int curX = curPos.first + nextP[i][0];
                    int curY = curPos.second + nextP[i][1];
                    if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                        continue;
                    if(grid[curX][curY] == 1){
                        flag = true;
                        grid[curX][curY] = 2;
                        q.push(make_pair(curX, curY));
                    }
                }
            }
            if(flag)
                ++step;
        }

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1)
                    return -1;
            }
        }

        return step;
    }
};

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int step = 1;
        unordered_set<string> book;
        unordered_set<string> dict;
        book.insert(beginWord);
        for(string& ch : wordList)
            dict.insert(ch);
        queue<string> q;
        q.push(beginWord);

        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == endWord)
                    return step;
                for(int i = 0; i < curStr.size(); i++){
                    string str1 = curStr;
                    for(char ch = 'a'; ch <= 'z'; ++ch){
                        str1[i] = ch;
                        //判断新的单词是否在词典中，且没被搜索过
                        if(dict.find(str1) != dict.end()
                        && book.find(str1) == book.end()){
                            q.push(str1);
                            book.insert(str1);
                        }
                    }
                }
            }
            ++step;
        }
        
        return 0;
    }
};

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deaddict(deadends.begin(), deadends.end());
        //如果0000在死亡数字中，则永远也到不了
        if(deaddict.find("0000") != deaddict.end())
            return -1;
        queue<string> q;
        q.push("0000");
        //添加标记，已经搜索过的字符不再搜索
        unordered_set<string> book;
        book.insert("0000");
        int step = 0;
        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == target)
                    return step;
                for(int i = 0; i < 4; i++){
                    string s1 = curStr;
                    string s2 = curStr;
                    //向前或向后旋转
                    s1[i] = s1[i] =='0' ? '9' : --s1[i];
                    s2[i] = s2[i] =='9' ? '0' : ++s2[i];
                    if(deaddict.find(s1) == deaddict.end()
                    && book.find(s1) == book.end()){
                        q.push(s1);
                        book.insert(s1);
                    }
                    if(deaddict.find(s2) == deaddict.end()
                    && book.find(s2) == book.end()){
                        q.push(s2);
                        book.insert(s2);
                    }
                }
            }
            ++step;
        }

        return -1;
    }
};