title: LC101の5. 搜索
urlname: kd8ewx
date: ‘2021-06-12 09:18:33’
tags: [DFS, BFS]
categories: [算法刷题]

深度优先搜索

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍
历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，
由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

深度优先搜索也可以用来检测环路，有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这 种做法叫做状态记录或记忆化（memoization）。

题目

695. 岛屿的最大面积

题目大意：用 1 表示岛屿，0 表示海，统计最大岛屿的面积（假设四周都是海）
LC101の5. 搜索 - 图1如图有 6 个岛屿
思路：
栈

  1. class Solution {
  2. public:
  3.     vector<int> direction{-1, 0, 1, 0, -1};
  4.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  5.         int m = grid.size(), n = grid[0].size();
  6.         int max_area = 0, local_area;
  7.         if(m == 0 && n == 0){
  8.             return 0;
  9.         }
  10.         for(int i = 0; i < m; i++){
  11.             for(int j = 0; j < n; j++){
  12.                 //一处岛屿的起点
  13.                 if(grid[i][j]){
  14.                     //初始化该处面积
  15.                     local_area = 1;
  16.                     stack<pair<int, int>> island;
  17.                     island.push({i,j});
  18.                     grid[i][j] = 0;
  19.                     //通过stack遍历当前岛屿各点
  20.                     while(!island.empty()){
  21.                         auto [q,p] = island.top();
  22.                         island.pop();
  23.                         //遍历上下左右
  24.                         for(int k = 0; k < 4; k++){
  25.                             int x = q + direction[k], y = p + direction[k + 1];
  26.                             //在边界内且值为1
  27.                             if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){
  28.                                 island.push({x,y});
  29.                                 local_area++;
  30.                                 grid[x][y] = 0;
  31.                             }
  32.                         }
  33.                     }
  34.                     max_area = max(local_area, max_area);
  35.                 }
  36.             }
  37.         }
  38.         return max_area;
  39.     }
  40. };

回溯

547. 省份数量

题目大意：
思路：

  1. class Solution {
  2. public:
  3.     int findCircleNum(vector<vector<int>>& isConnected) {
  4.         int n  = isConnected.size(), count = 0;
  5.         vector<bool> visited(n, false);
  6.         for(int i = 0; i < n; i++){
  7.             //未访问结点
  8.             if(!visited[i]){
  9.                 dfs(isConnected, i, visited);
  10.                 count++;
  11.             }
  12.         }
  13.         return count;
  14.     }
  15.     //辅函数：遍历相连节点，做状态记录
  16.     void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited){
  17.         visited[i] = true;
  18.         for(int j = 0; j < isConnected.size(); j++){
  19.             if(isConnected[i][j] == 1 && !visited[j]){
  20.                 dfs(isConnected, j, visited);
  21.             }
  22.         }
  23.     }
  24. };

417. 太平洋大西洋水流问题

题目大意：如下图矩阵，左上角两边表示太平洋，右下角表示大西洋，矩阵各单元表示一块陆地，数字表示该陆地的高度，洋流仅可以从高处流往低处，找出所有既可以流到大西洋也可以流到太平洋的陆地单元。
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5)
~ 3 2 3 (4) (4)
~ 2 4 (5) 3 1
~ (6) (7) 1 4 5
~ (5) 1 1 2 4 大西洋
思路：

  1. class Solution {
  2. public:
  3.     vector<int> direction{-1, 0, 1, 0, -1};
  4.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
  5.         int m = heights.size(), n = heights[0].size();
  6.         if(m == 0 || n == 0){
  7.             return {};
  8.         }
  9.         vector<vector<int>> ans;
  10.         vector<vector<bool>> vistited_a(m,vector<bool>(n, false));
  11.         vector<vector<bool>> vistited_b(m,vector<bool>(n, false));
  12.         for(int i = 0; i < m; i++){
  13.             //左右边框
  14.             dfs(heights, vistited_a, i, 0);
  15.             dfs(heights, vistited_b, i, n - 1);
  16.         }
  17.         for(int j = 0; j < n; j++){
  18.             //上下边框
  19.             dfs(heights, vistited_a, 0, j);
  20.             dfs(heights, vistited_b, m - 1, j);
  21.         }
  22.         for(int i  = 0; i < m; i++){
  23.             for(int j = 0; j < n; j++){
  24.                 if(vistited_a[i][j] && vistited_b[i][j]){
  25.                     ans.push_back(vector<int>{i,j});
  26.                 }
  27.             }
  28.         }
  29.         return ans;
  30.     }
  31.     void dfs(const vector<vector<int>>& heights, vector<vector<bool>>& visited, int r, int c){
  32.         if(visited[r][c]){
  33.             return;
  34.         }
  35.         visited[r][c] = true;
  36.         for(int i = 0; i < 4; i++){
  37.             int x = r + direction[i], y = c + direction[i + 1];
  38.             if(x >= 0 && x < heights.size() && y >= 0 && y < heights[0].size() &&
  39.              heights[r][c] <= heights[x][y]){
  40.                 dfs(heights, visited, x, y);
  41.             }
  42.         }
  43.     }
  44. };

回溯法

回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

46. 全排列

  1. class Solution {
  2. public:
  3.     vector<vector<int>> permute(vector<int>& nums) {
  4.         vector<vector<int>> ans;
  5.         back(nums, 0, ans);
  6.         return ans;
  7.     }
  8.     void back(vector<int> &nums, int level, vector<vector<int>> &ans){
  9.         if(level == nums.size() - 1){
  10.             ans.push_back(nums);
  11.             return;
  12.         }
  13.         for (int i = level; i < nums.size(); i++) {
  14.             swap(nums[i], nums[level]);
  15.             back(nums, level+1, ans);
  16.             swap(nums[i], nums[level]);
  17.         }
  18.     }
  19. };

77. 组合

79. 单词搜索

51. N 皇后

广度优先搜索

广度优先搜索（breadth-fifirst search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因
此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时
按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。