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

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

class Solution {
public:
    int DFS(unordered_map<int, Employee*>& info, int id)
    {
        int curImpo = info[id]->importance;
        for(const auto& sid : info[id]->subordinates)
        {
            curImpo += DFS(info, sid);
        }

        return curImpo;
    }

    int getImportance(vector<Employee*> employees, int id) {
        if(employees.empty())
            return 0;
        unordered_map<int, Employee*> info;
        for(const auto& e : employees)
        {
            info[e->id] = e;
        }

        return DFS(info, id);
    }
};

图像渲染

问题描述：

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

解题思路:

从所给坐标开始，向上下左右四个方向渲染，只要渲染点的颜色值和原坐标相同，则继续向外渲染。 边界：位置是否越界。

这里需要用标记避免重复修改，使时间复杂度不超过O(row*col)

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

class Solution {
public:
    void DFS(vector<vector<int>>& image, vector<vector<int>>& book, int sr, int sc, int newColor, int oldColor, int row, int col)
    {
        image[sr][sc] = newColor;
        book[sr][sc] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = sr + nextP[i][0];
            int curY = sc + nextP[i][1];

            //判断是否越界
            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            //颜色符合要求且之前没被渲染过则继续渲染
            if(image[curX][curY] == oldColor && book[curX][curY] == 0)
            {
                DFS(image, book, curX, curY, newColor, oldColor, row, col);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int row = image.size();
        int col = image[0].size();
        int oldColor = image[sr][sc];
        vector<vector<int>> book(row, vector<int>(col, 0));

        DFS(image, book, sr, sc, newColor, oldColor, row, col);

        return image;
    }
};

被围绕的区域

问题描述：

给你一个 m x n 的矩阵 board ，由若干字符 ‘X' 和 ‘O' ，找到所有被 ‘X' 围绕的区域，并将这些区域里所有的 ‘O' 用 ‘X' 填充。

解题思路： 从每个边缘的O开始，只要和边缘的O连通，则它就没有被包围。

1.首先寻找边上的每一个O，如果没有，表示所有的O都被包围。

2.对于边上的每一个O进行dfs扩散，先把边上的每一个O用特殊符号标记（除了X和O以外）。把和它相邻的O都替换为特殊符号，每一个新的位置都做相同的dfs操作。

3.所有扩散结束之后，把特殊符号的位置（和边界连通）还原为O，原来为O的位置（和边界不连通）替换为X即可。

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

class Solution {
public:
    void DFS(vector<vector<char>>& board, int curX, int curY, int row, int col)
    {
        board[curX][curY] = 'A';
        for(int i = 0; i < 4; i++)
        {
            int x = curX + nextP[i][0];
            int y = curY + nextP[i][1];

            if(x < 0 || x >= row
               ||y < 0 || y >= col)
                continue;

            if(board[x][y] != 'A' && board[x][y] != 'X')
                DFS(board, x, y, row, col);
        }
    }

    void solve(vector<vector<char>>& board) {
        if(board.empty())
            return;
        int row = board.size();
        int col = board[0].size();

        //第一行和最后一行
        for(int i = 0; i < col; i++)
        {
            if(board[0][i] == 'O')
                DFS(board, 0, i, row, col);
            if(board[row-1][i] == 'O')
                DFS(board, row-1, i, row, col);
        }
        //第一列和最后一列
        for(int i = 0; i < row; i++)
        {
            if(board[i][0] == 'O')
                DFS(board, i, 0, row, col);
            if(board[i][col-1] == 'O')
                DFS(board, i, col-1, row, col);
        }

        for(int i = 1; i < row-1; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == 'A')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};

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

class Solution {
public:
    void DFS(vector<vector<char>>& grid, vector<vector<int>>& book, int x, int y, int row, int col)
    {
        book[x][y] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = x + nextP[i][0];
            int curY = y + nextP[i][1];

            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            
            if(grid[curX][curY] == '1' && book[curX][curY] == 0)
                DFS(grid, book, curX, curY, row, col);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())
            return 0;
        int row = grid.size();
        int col = grid[0].size();
        int num = 0;
        vector<vector<int>> book(row, vector<int>(col, 0));
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == '1' && book[i][j] == 0)
                {
                    ++num;
                    DFS(grid, book, i, j, row, col);
                }
            }
        }

        return num;
    }
};