Summary of leetcode BFS question brushing

I haven't written a summary of brush questions during this period , Because of the discovery BFS It will be a little difficult to deal with the problem .

From the basic point of view ,BFS（breath first search） Width first search . Is to traverse layer by layer .

BFS Several main applications of ：

1. Traversing the tree hierarchically .

2. Traversal of graph hierarchically .、

3. The array is traversed hierarchically .

For these three different applications , About the framework of problem solving （ General idea ）

1. For the problem to traverse according to the hierarchy , This is simpler .

        a. There is a direction between the upper node and the lower node in the tree , For example, the parent node will point to the child node .

        b. Because there is direction , There will be no undirected graph that points around and points to itself .

Its general framework is as follows ：

i. initialization queue( Traversal by level must use queue), For example root push To queue Go inside to initialize queue.

ii. Record the number of elements in the current layer , Out of the queue in turn . And put the left and right children out of the queue into the queue at the same time .

iii. Go through the descendants layer by layer , Know that the queue is empty .

For the problem of traversing the tree according to the hierarchy , The solution framework is fixed . Don't bother .

2. For the hierarchical traversal of graphs

These problems are somewhat complicated , In particular, undirected graphs . Deal with the data in advance .

1. To extract into each element neighbors data , Then you can traverse layer by layer neighbor.

2. To initialize queue, You have to find the initialization queue The data of . That is, the data to be accessed first , For example, the first course in the topic of course selection .

3. use BFS Layer by layer traversal neighbor, And check whether you have visited before . An undirected graph has no direction ,A yes B Neighbors of , meanwhile B It's also A Neighbors of . If you don't check the duplicate , It will lead to an endless cycle .

For example, the topic of course selection . Some courses must be completed before taking later courses .

Like the introduction to algorithms, you can only repair advanced algorithms or advanced databases after you finish it .

207. Course Schedule

The framework is as follows ：

1. Create subsequent courses for each course

2. Create the entry level of each course （ Preface course ）.

3. initialization queue The element of is in degree 0 Curriculum （ First course ）

4. BFS Visit the courses to be taken next semester layer by layer ,. The completion of the first floor in the queue means that the courses of this semester have been completed , Subtract the entry of all subsequent courses pointed to by the previous course 1, It represents that the previous course in the course of next semester has been completed .

5. When the entry level of this course is 0, Represents that you have completed all the introductory courses . You can put the course in the queue , It means that this course has been completed since the beginning of this semester .

3、 ... and , For the coordinate system / Hierarchical traversal of arrays .

Such a topic is also similar to graph traversal , for instance , such as 2101. Detonate the Maximum Bombs

The topic is if a bomb explodes , All mines in the explosion range will explode . Then find out how many mines can explode at most at one time .

Steps are as follows ：

1. Find out the other mines within the explosion range of each mine , That is, its follow-up mines .

2. Now we have to consider which mines to put queue in , Detonate first .

      Because I don't know which mine detonates first, it will detonate more mines , So I can only try one by one .

      But you can't try every one foolishly , When you light a thunder , The mines detonated in turn within the detonating range are also removed from the array of mines to be tried . In this way, the number of mines to be tried is much less .

But this topic uses BFS There is also a bad point in doing it , That is checking the weight .

unorder_set perhaps unorder_map I won't support it pair As key. For example, the positions of coordinate points or arrays are x,y Two figures .

This pair of data is used pair After packaging , There's no way pair Most of all key To apply hash.

These questions are best used DP To do it , In this way, the coordinate position can be recorded .

The code is as follows

class Solution {
public:
    unordered_map<int, vector<int>> buildGraph(vector<vector<int>>& bombs)
    {
        unordered_map<int, vector<int>> graph;
        
        for(int i=0;i<bombs.size();i++){
            long ix= bombs[i][0];
            long iy= bombs[i][1];
            long ir= bombs[i][2];
            
            for(int j=0;j<bombs.size();j++){
                if(j == i)
                    continue;
                
                long jx= bombs[j][0];
                long jy= bombs[j][1];
                
                if( (jx-ix)*(jx-ix) + (jy-iy)*(jy-iy) <= ir*ir )
                    graph[i].push_back(j);
            }
        }
        
        return graph;
    }
    
    int detonateBombs(int start, unordered_map<int, vector<int>> neighbors)
    {
        int ret=1;
        queue<int> myqueue;
        unordered_set<int> bombed;
        
        bombed.insert(start);
        myqueue.push(start);
        
        while(!myqueue.empty()){
            int size = myqueue.size();
            
            for(int i=0;i<size;i++){
                int cur = myqueue.front();
                myqueue.pop();
                
                for(auto neighbor: neighbors[cur]){
                    if(bombed.find(neighbor) != bombed.end())
                        continue;
                    else {
                        myqueue.push(neighbor);
                        bombed.insert(neighbor);
                        ret++;
                    }
                }
            }
        }
        return ret;
    }
    
    int maximumDetonation(vector<vector<int>>& bombs) {
        // build a graph which bombs in the range of bombs A.
        // BFS each bombs to get all the other bombs.
        // go through all bombs as start bombs.
        
        unordered_map<int, vector<int>> graph = buildGraph(bombs);
        int maxBombs=0;
        int tmp=0;
        
        for(int start =0;start<bombs.size();start++) {
            tmp = detonateBombs(start, graph);
            if(tmp > maxBombs)
                maxBombs = tmp;
        }
        
        return maxBombs;
    }
};