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>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
int max_area = 0;
for(int i=0; i for(int j=0; j max_area = max(max_area, dfs(grid, i, j));
}
}
return max_area;
}
int dfs(vector>& 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>& isConnected){
int n=isConnected.size(), count=0;
vector visited(n, false);
for(int i=0; i if(!visited[i]){
dfs(isConnected, i, visited);
//一趟dfs后，所有与i相连的城市就都找到了
count++;
}
}
return count;
}
//辅函数
void dfs(vector>& isConnected, int i, vector& visited){
visited[i]=true;
for(int j=0;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> permute(vector& nums) {
vector> ans;
backtracking(nums, 0, ans);
return ans;
}
//辅函数
void backtracking(vector &nums, int level, vector> &ans){
if(level == nums.size()-1){ //for循环结束就把排列后的nums push_back到ans里
ans.push_back(nums);
return;
}
for(int i=level; 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> combine(int n, int k){
vector> result;
vector path;
backtracting(result, path, n, k, 1);
return result;
}
void backtracting(vector>& result,vector& 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 < }
}
/*
那么为什么还会用到回溯的，我们想下，如果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>& board, string word) {
if(board.empty()) return false;
int m=board.size(),n=board[0].size();
vector> visitied(m,vector(n,false)); //用来标记当前点，状态矩阵
bool find=false;
for(int i=0; i for(int j=0; j backtracting(i, j, board, word, visitied, 0, find);
}
}
return find;
}
void backtracting(int i, int j, vector>& board, string& word, vector>& 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> solveNQueens(int n){
vector> ans; //结果
if(n == 0){
return ans;
}
vector board(n, string(n, '.')); //string 数组 初始化 棋盘
vector 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> &ans, vector &board, vector &column,
vector& ldiag, vector &rdiag, int row, int n){
//返回条件
if(row == n){
ans.push_back(board);
return;
}
for(int i=0; i 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 direction{-1, 0, 1, 0, -1};
//主函数
int shortestBridge(vector>& grid) {
int m=grid.size(), n=grid[0].size();
queue

> points; //广度优先遍历会用队列queue来解决这类问题
//dfs寻找第一个岛屿，并把1全部赋值为2
bool flipped=false; //
for(int i=0; i if(flipped) break;
for(int j=0; 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 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

>& points, vector>& 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);
}