5.搜索-dfs、回溯、bfs

/*
深度优先搜索(dfs)和广度优先搜索(bfs)是两种最常见的优先搜索方法，它们被广泛的运用在图和树等结构中进行搜索。
    主要使用的技术为：栈与递归、递归与回溯、队列
*/

/*
深度优先搜索(depth-first search,DFS)：主要使用“栈与递归”的算法
    在搜索到一个新的节点时，立即对该节点进行遍历；因此遍历需要先入后出的栈来实现，也可以通过与栈等价的递归来实现。
*/

//695.最大岛屿面积
/*
题目描述：给定一个二维的0-1矩阵，其中0表示海洋，1表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子
相邻。求最大的岛屿面积。
输入输出：输入是一个二维数组，输出是一个整数，表示最大岛屿面积。
Input：
[[1,0,1,1,0,1,0,1],
 [1,0,1,1,0,1,1,1],
 [0,0,0,0,0,0,0,1]]
 Output:6
题解:递归调用，辅函数为深度优先的递归写法，找到陆地，查看陆地上下左右是否为陆地，如果是则岛屿面积+1，并记得沉没此块陆地，防止被重复搜索到。
*/
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if(grid.empty() || grid[0].empty()) return 0;
    int max_area = 0;
    for(int i=0; i<grid.size(); i++){
        for(int j=0; j<grid[0].szie(); j++){
            max_area = max(max_area, dfs(grid, i, j));
        }
    }
    return max_area;
}
int dfs(vector<vector<int>>& grid, int i, int j){
    if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]==0){
        return 0;
    }
    grid[i][j]=0;   //沉没此块陆地
    return 1+dfs(grid, i-1, j)+dfs(grid, i, j-1)+dfs(grid, i+1, j)+dfs(grid, i, j+1);   //寻找周围相连陆地
}


//547.省份数量
/*
题目描述：有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。
    省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个n*n的矩阵isConnected, 其中isConnected[i][j]=1，表示第i个
城市和第j个城市直接相连，而isConnected[i][j]=0表示二者不直接相连。返回矩阵中省份的数量。
和最大岛屿面积一摸一样啊。
*/
//主函数
int findCircleNum(vector<vector<int>>& isConnected){
    int n=isConnected.size(), count=0;
    vector<bool> visited(n, false);
    for(int i=0; i<n; i++){
        if(!visited[i]){
            dfs(isConnected, i, visited);
            //一趟dfs后，所有与i相连的城市就都找到了
            count++;
        }
    }
    return count;
}
//辅函数
void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited){
    visited[i]=true;
    for(int j=0;j<isConnected.size();j++){
        //如果城市i与城市j相连，并且j没有被访问过，那就进行递归找到与j相连的城市，最终vistied为与i可以访问的所有城市
        if(isConnected[i][j] == 1 && !visited[j]){
            dfs(isConnected, j, visited);
        }
    }
}


/*
回溯法：https://www.bilibili.com/video/BV1cy4y167mM  系列视频
回溯法（backtracking）是优先搜索的一种特殊情况，又称试探法（或穷举法、暴力搜索），常用于需要记录节点状态的深度优先搜索。
通常来说，排列、组合、选择类问题使用回溯法比较方便。
顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点
继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。

*/

//46.全排列：https://www.bilibili.com/video/BV1dx411S7WR?from=search&seid=6705623231078872903
/*
题目描述：给定一个无重复数字的整数数组，求其所有的排列方式。
Input:[1,2,3]
Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
可以以任意顺序输出，只包含了所有排列方式即可。
题解：
怎样输出所有的排列方式呢？对于每一个当前位置i，我们可以将其与之后的任意位置交换，然后继续处理i+1，直到处理到最后一位。为了防止
我们每次遍历时都要新建一个子数组存储位置i之前已经交换好的数字，我们可以利用回溯法，只对原数组进行修改，在递归完成后再修改回来。
我们以样例[1,2,3]为例，按照这种方法，我们输出的数组顺序为[[1,2,3][1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]],可以看到
所有的排列在这个算法中都被考虑到了。
*/
//主函数
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    backtracking(nums, 0, ans);
    return ans;
}
//辅函数
void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans){
    if(level == nums.size()-1){ //for循环结束就把排列后的nums push_back到ans里
        ans.push_back(nums);
        return;
    }
    for(int i=level; i<nums.size(); i++){
        swap(nums[i], nums[level]);     //把下标为i的数组提到前边（level）去
        backtracking(nums, level+1, ans);   //剩余的数组再做全排列
        swap(nums[i], nums[level]);     //回改当前节点状态，接着进行for循环
    }
}


//77.组合
/*
题目描述：
给定一个整数n和一个整数k，求在1到n中选取k个数字的所有组合方法
输入输出样例：
Input: n=4, k=2
Output:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
这里二维数组的每个维度都可以以任意顺序输出
题解：类似于排列问题，我们也可以进行回溯。排列回溯的是交换的位置，而组合回溯的是否把当前的数字加入结果中。
*/

//主函数
vector<vector<int>> combine(int n, int k){
    vector<vector<int>> result;
    vector<int> path;
    backtracting(result, path, n, k, 1);
    return result;
}
void backtracting(vector<vector<int>>& result,vector<int>& path,int n,int k, int start){
    //终止条件
    if(path.size() == k){
        result.push_back(path);
        return; //仅跳出当前回溯分支
    }
    //for循环
    for(int i=start; i<=n; i++){
        path.push_back(i);    //子队列赋值
        backtracting(result, path, n, k, i+1); //递归
        path.pop_back();
    }
}

//此题n=4,k=2 可以用两个for循环就能解决，如下
for(int i=1; i<=4; i++){
    for(int j=i+1; j<=4; j++){
        cout << i << " " << j << endl;
    }
}
/*
那么为什么还会用到回溯的，我们想下，如果k=3，那么我们是不是还要加一个for循环
如果n=100,k=50呢，写50个for循环......?
那么用回溯就能轻松解决，只需改下传递的参数就可以喽
是不是瞬间感觉这些算法还是很有用的？
*/


//79.单词搜索
/*
题目描述：给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求字符串能不能在字母矩阵中寻找到。
和岛屿面积有点像
输入输出样例：
输入是一个二维字符数组和一个字符串，输出是一个布尔值，表示字符串是否可以被寻找到。
Input: word="ABCCED",board=
[[‘A‘,‘B‘,‘C‘,‘E‘],
[‘S‘,‘F‘,‘C‘,‘S‘],
[‘A‘,‘D‘,‘E‘,‘E‘]]
Output:true
从坐上角‘A’开始，我们可以先向右、再向下、最后向左，找到连续的“ABCCED”
不同于排列组合问题，本题采用的并不是修改输出方式，而是修改访问标记。在我们对任意位置进行深度优先搜索时，我们先标记当前位置为已访问，
以避免重复遍历（如防止向右搜索后又向左返回）；在所有的可能都搜索完成后，再改回当前位置为未访问，防止干扰其他位置搜索到当前位置。
使用回溯法，我们可以只对一个二维的访问矩阵进行修改，而不用把每次的搜索状态作为一个新对象传入递归函数中。
*/

bool exist(vector<vector<char>>& board, string word) {
    if(board.empty()) return false;
    int m=board.size(),n=board[0].size();
    vector<vector<bool>> visitied(m,vector<bool>(n,false));      //用来标记当前点，状态矩阵
    bool find=false;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            backtracting(i, j, board, word, visitied, 0, find);
        }
    }
    return find;
}
void backtracting(int i, int j, vector<vector<char>>& board, string& word, vector<vector<bool>>& visitied, int pos, bool &find){
    //条件判断
    if(i<0 || i>=board.size() || j<0 || j>= board[0].size()){    //判断是否越界
        return;
    }
    if(find || visitied[i][j] || board[i][j]!=word[pos]){       //判断是否是否匹配
        return;
    }
    if(pos==word.size()-1){  //是否匹配完成
        find=true;
        return;
    }
    visitied[i][j]=true;    //匹配成功，沉没此点
    //上下左右递归
    backtracting(i-1, j, board, word, visitied, pos+1, find);
    backtracting(i+1, j, board, word, visitied, pos+1, find);
    backtracting(i, j-1, board, word, visitied, pos+1, find);
    backtracting(i, j+1, board, word, visitied, pos+1, find);
    visitied[i][j]=false;   //匹配成功，恢复沉没点
}


//51.N(8)-皇后
/*hard*/
/*
题目描述：给定一个大小为n的正方形国际象棋棋盘，求有多少种方式可以放置n个皇后并使得她们互不攻击，即每一行、列、左斜、右斜
最多只有一个皇后。
输入输出：输入是一个整数n，输出是一个二维字符串数组，表示所有的棋盘表示方法。
题解：类似于在矩阵中寻找字符串，本题也是通过修改状态矩阵来进行回溯。不同的是，我们需要对每一行、列、左斜、右斜建立访问数组，
来记录它们是否存在皇后。本题有一个隐藏的条件，即满足条件的结果中每一行或列有且仅有一个皇后。这是因为我们一共只有n行和n列。
所以如果我们通过对每一行遍历来插入皇后，我们就不需要对行建立访问数组了。
*/

//主函数
vector<vector<string>> solveNQueens(int n){
    vector<vector<string>> ans;     //结果
    if(n == 0){
        return ans;
    }
    vector<string> board(n, string(n, ‘.‘));    //string 数组 初始化 棋盘
    vector<bool> column(n,false), ldiag(2*n-1, false), rdiag(2*n-1, false);   //列，左斜，右斜
    backtracking(ans, board, column, ldiag, rdiag, 0, n);
    return ans;
}
//辅函数
void backtracking(vector<vector<string>> &ans, vector<string> &board, vector<bool> &column,
    vector<bool>& ldiag, vector<bool> &rdiag, int row, int n){
    //返回条件
    if(row == n){
        ans.push_back(board);
        return;
    }
    for(int i=0; i<n; i++){         //i为列(row)的索引
        if(column[i] || ldiag[n-row+i-1] || rdiag[row+i+1]) {
            continue;
        }
        //修改当前节点状态
        board[row][i] = ‘Q‘;
        column[i] = ldiag[n-row+i-1] = rdiag[row+i+1] = true;
        //递归子节点
        backtracking(ans, board, column, ldiag, rdiag, row+1, n);
        //回改当前节点状态
        board[row][i]=‘.‘;
        column[i] = ldiag[n-row+i-1] = rdiag[row+i+1] = false;
    }
}


//bfs 广度优先搜索 主要使用队列queue“先进先出”来处理  处理二叉树问题用的较多，之后的二叉树章节会有更多题目
/*
广度优先搜索不同于深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层进行遍历，广度优先搜索时按照
“广”的方向进行遍历的，也常常用来处理最短路径等问题。
考虑如下一颗简单的树。我们从1号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着“广”的方向前进的策略，队列顶端的元素变换过程
[1]->[2->3]->[4],其中方括号代表每一层的元素。
*/

//934.最短的桥
/*
题目描述：给定一个二维0-1矩阵，其中1表示陆地，0表示海洋，每个位置与上下左右相连。已知矩阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个
岛屿相连。
输入输出样例：输入是一个二维数组，输出是一个非负整数，表示需要填海造陆的位置数。
Input:
[[1,1,1,1,1]
 [1,0,0,0,1]
 [1,0,1,0,1]
 [1,0,0,0,1]
 [1,1,1,1,1]]
Output:1
题解：本题实际上是求两个岛屿间的最短距离，因此我们可以先通过任意搜索方法找到其中一个岛屿，然后利用广度优先搜索查找与另一个岛屿的最短距离。
*/

vector<int> direction{-1, 0, 1, 0, -1};
//主函数
int shortestBridge(vector<vector<int>>& grid) {
    int m=grid.size(), n=grid[0].size();
    queue<pair<int, int>> points;       //广度优先遍历会用队列queue来解决这类问题
    //dfs寻找第一个岛屿，并把1全部赋值为2
    bool flipped=false;         //
    for(int i=0; i<m; i++){
        if(flipped) break;
        for(int j=0; j<n; j++){
            if(grid[i][j] == 1){
                dfs(points, grid, m, n, i, j);
                flipped=true;
                break;
            }
        }
    }
    //bfs寻找第二个岛屿，并把过程中经过的0赋值为2
    int x,y;
    int level=0;
    while(!points.empty()){
        ++level;
        int n_points=points.size();
        while(n_points--){
            auto [r,c] = points.front();
            points.pop();
            for(int k=0; k<4; k++){
                x=r+dirction[k], y=c+dirction[k+1];
                if(x>=0 && y>=0 && x<m && y<n){
                    if(grid[x][y]==2){
                        continue;
                    }
                    if(grid[x][y]==1){
                        return level;
                    }
                    points.push({x,y});
                    grid[x][y] = 2;
                }
            }
        }
    }
    return 0;
}

//辅函数
void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int m, int n, int i, int j){
    if(i<0 || i>=m || j<0 || j>=n || grid[i][j]==2){
        return;
    }
    if(grid[i][j]==0){
        points.push({i,j});
        return;
    }
    grid[i][j]==2;
    dfs(points, grid, m, n, i-1, j);
    dfs(points, grid, m, n, i+1, j);
    dfs(points, grid, m, n, i, j-1);
    dfs(points, grid, m, n, i, j+1);
}