最短时间学会基于C++实现DFS深度优先搜索

目录

• 前言
• 1.迷宫找出口,区分dfs,bfs：
• 一、DFS经典放牌可能组合
• 二、leetcode 员工的重要性
• 三、leetcode 图像渲染
• 四、leetcode 被围绕的区域
• 五、岛屿数量
• 六、 小练习：岛屿的最大面积
• 总结

//处理第index个盒子 _ - - 并行递归，n有多大我们就调用多少次
DFS(vector<int>& box,int index,vector<int>& visited,int n)
{//box为盒子，index为当前盒子，visited为标记哪张牌用了的数组，n为处理几张牌
	if(index == n+1)//每一个盒子都有牌了
	{
		return;
	}
	for(int i =1;i<n;++i)
	{
		if(visited[i]==0)
		{
			//表示没有用过的牌就可以放在当前的盒子当中
			box[index] = i;//当前的盒子放这张牌
			visited[i] =1 ;
			//这里的逻辑就是我们站在一个盒子，我们按照我们手中的牌，从小到大依次尝试
			//到这里我们就处理下一个盒子
			DFS(box,index+1,visited,n);
			//一种方法完成，我们就回收牌
			visited[i]=0;//标记成0就可以再次使用啦！
		}
	}
}

void DFS(int index, int n, vector<int>& box, vector<int>& visited)
{
	//处理当前的盒子

	//我们这里打印看看每个盒子装的都是什么
	if (index == n + 1)
	{
		for (int i=1;i<box.size();++i)
			cout << box[i] << " ";
		cout << endl;
		
		//表示每个盒子我们都已经放满了东西，我们就可以返回上一层
		return;
	}

	//每个盒子都要用n张牌来看看是否能够使用，按照我们从小到大使用的规定原则
	for (int i = 1; i <= n; ++i)
	{
		//表示牌没有被用过，可以使用
		if (visited[i] == 0)
		{
			box[index] = i;//表示在看到index个盒子的时候，我们用第i张牌放入
			
			visited[i] = 1;//标记当前牌已经被使用
			//走到这里我们当前这个盒子该干的事情已经干完了，我们就可以处理下一个盒子

			DFS(index + 1, n, box, visited);
			//表示所有的牌都已经放入并且返回，这时我们回收牌
			visited[i] = 0;
		}
	}
}
int main()
{
	int n;
	vector<int> box;
	vector<int> vistied;
	cin >> n;
	box.resize(n + 1, 0);
	vistied.resize(n + 1, 0);
	//这里的1是我们当前走到盒子，n是我们有多少牌，boxs是我们用来存放的盒子，	
	//visited是用来确定是否访问过的标记矩阵
	DFS(1, n, box, vistied);
	return 0;
}

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        
    }
};

for(int id: um[id]->subordinates)
        {
            //对于当前我们需要sum加上加上当前id的重要度
            sum += um[id]->importance;
            //遍历当前id的所有直系下属
            DFS(id,um,sum);
        }

// 题目答案:
class Solution {
public: 
    void DFS(int id,unordered_map<int,Employee*>& um,int& sum)
    {
        //对于每一个id，下属的id都会有属于他们的vector<int> subordinates;
        //所以我们都要去遍历当前id的subordinates
        for(int id: um[id]->subordinates)
        {
            //对于当前我们需要sum加上加上当前id的重要度
            sum += um[id]->importance;
            //遍历当前id的直系下属(**一路走到黑**),统计完的结果放到sum当中
            DFS(id,um,sum);
        }
    }
    
    int getImportance(vector<Employee*> employees, int id) {
        //单个员工 id ，返回这个员工和他所有下属的重要度之和。
        //DFS:深度遍历这个员工的旗下所有重要度之和，这题适合一条路走到黑
        //因为在vector中的查找都是O（N）的时间复杂度，我们选择用哈希表，并且将id与员工的指针建立映射,因为我们在DFS中要使用到用id找到员工
        unordered_map<int,Employee*> um;
        for(Employee* e : employees)
        {
            //将employees的数据导入us（哈希表中）
            um[e->id] = e;
        }
        int sum = um[id]->importance;//提前加上当前id的重要度
        //dfs是遍历当前id的subordinates的重要度
        DFS(id, um,sum);
        return sum;
    }
};

int arr[4][2] ={{1,0},{0,1},{-1,0},{0,-1}};//方向矩阵
    void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,int row ,int col,int oldcolor)
    {
        image[curX][curY] = newColor;//上色
        //遍历 (sr，sc)的上下左右 -- 我们可以设置一个全局的方向矩阵
        for(int i=0;i<4;++i)
        {
            //(newX,newY)就是该点的上下左右了
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            if(newX<0||newX>=row
            ||newY<0||newY>=col)
            continue;//表示新的坐标越界了不符合要求，跳过
            
            //走到这里表示新的坐标没有问题,如果是就颜色我们就上色
            if(image[newX][newY] == oldcolor)
            {     
                //当前的点处理完，我们处理下一个点
                DFS(image,newX,newY,newColor,row,col,oldcolor);
            }
            else
            continue;        
        }
    }

int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
    void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,vector<vector<int>>& visited,int row ,int col,int oldColor)
    {
        //给当前位置染色
         image[curX][curY] = newColor;
         //标记当前位置已经使用了
         visited[curX][curY]=1;

        
        //遍历 (sr，sc)的上右下左 -- 我们可以设置一个全局的方向矩阵
        for(int i=0;i<4;++i)
        {
            //(newX,newY)就是该点的上下左右了
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            //判断新坐标是否合法
            if(newX<0 || newX>=row
            || newY<0 || newY>=col)
            continue;

            
            //如果是没有访问过的并且是旧颜色就递归这个点的周围
            if(visited[newX][newY] == 0 && 
               image[newX][newY] == oldColor)
                 DFS(image,newX,newY,newColor,visited,row,col,oldColor) ; 
               
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    //我们这道题也可以用BFS，DFS做都没问题，我们这里讲到DFS，所以就用DFS的思路解决
        int row = image.size();
        int col = image[0].size();
        int oldColor =image[sr][sc];
        //初始化标记矩阵，没访问过的置成0
        vector<vector<int>> visited(row,vector<int>(col,0));
        DFS(image,sr,sc,newColor,visited,row,col,oldColor);
        return image;
    }
};

int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
    void DFS(vector<vector<char>>& board,int row,int col,int curX,int curY)
    {
        //当前点就是联通的‘O"
        board[curX][curY] ="#";
        for(int i =0;i<4;++i)
        {
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            if(newX<0||newX>=row
            ||newY<0||newY>=col)
            continue;
            if(board[newX][newY]=="O")
            DFS(board,row,col,newX,newY);
        }
    }
    void solve(vector<vector<char>>& board) {
        //我们可以从每一个边界的O出发，链接的O就是不用改的，其他的都是要改成‘X"的
        //但是我们可以通过修改与外面相连的O暂时修改#，就不需要标记矩阵了
        int row =board.size();
        int col=board[0].size();
        for(int i=0;i<row;++i)
        {
            if(board[i][0] =="O")
            DFS(board,row,col,i,0);
            if(board[i][col-1] =="O")
            DFS(board,row,col,i,col-1);
        }
        for(int j =0;j<col;++j)
        {
            if(board[0][j]=="O")
            DFS(board,row,col,0,j);
            if(board[row-1][j]=="O")
            DFS(board,row,col,row-1,j);
        }
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(board[i][j]=="O")
                board[i][j]="X";
                if(board[i][j]=="#")
                board[i][j]="O";
            }
        }
        return ;
    }
};

int arr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
class Solution {
public:
    void DFS(vector<vector<int>>& visited,vector<vector<char>>& board,int row,int col,int curX ,int curY)
    {
        //与外界联通的还是O，我们标记为1
        visited[curX][curY] = 1;

        for(int i =0;i<4;++i)
        {
            int newx = curX+arr[i][0];
            int newy = curY+arr[i][1];
            if(newx<0||newx>=row||
            newy<0||newy>=col)
            continue;
            //没有被访问过的位置（防止重复递归）&& 为O的位置我们才递归
            if(visited[newx][newy]==0&&
            board[newx][newy]=="O")
            {
                DFS(visited,board,row,col,newx,newy);
            }       
        }
    }
    void solve(vector<vector<char>>& board) {
        //思路：我们从周围的O出发，与边界O DFS都能获取到的位置我们都可以做个标记
        //最后将标记的不动，没标记的换成"X"(内陆)。
        int row = board.size();
        int col=board[0].size();
        vector<vector<int>> visited(row,vector<int>(col,0));
        //遍历周围为O的位置
        //两列
        for(int i =0;i<row;++i)
        {
            if(board[i][0]=="O")
            DFS(visited,board,row,col,i,0);
            if(board[i][col-1]=="O")
            DFS(visited,board,row,col,i,col-1);       
        }
        //两行
        for(int j =0;j<col;++j)
        {
            if(board[0][j]=="O")
            DFS(visited,board,row,col,0,j);
            if(board[row-1][j]=="O")
            DFS(visited,board,row,col,row-1,j);    
        }
        //最后将没有标记的O换成X，标记了的不变
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(visited[i][j]==0)
                board[i][j] = "X";
                cout<<visited[i][j];
            }
        }
    }
};

int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
    void DFS(vector<vector<int>>& visited,vector<vector<char>>& grid,int row,int col,int curx,int cury)
    {
        //将当前位置标记为走过
        visited[curx][cury]=1;
        for(int i =0;i<4;++i)
        {
            int newx = curx+arr[i][0];
            int newy = cury+arr[i][1];
            if(newx<0||newx>=row||newy<0||newy>=col)
                continue;
            if(grid[newx][newy]=="1"&&visited[newx][newy]==0)
            DFS(visited,grid,row,col,newx,newy);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        //这道题其实也是用BFS，DFS都可以解，用DFS的话我的思路是从第一个开始遍历，遇到一个visited没有访问过的1就去遍历他的上下左右，将他周围的1都遍历，在将次数加一
        int row =grid.size();
        int col=grid[0].size();
        int count =0;
        vector<vector<int>> visited(row,vector<int>(col,0));
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(visited[i][j]==0&&grid[i][j]=="1")
                {
                    DFS(visited,grid,row,col,i,j);
                    count++;
                }
            }
        }
        return count;
    }
};