目录
一、深度搜索
841. 钥匙和房间
岛屿系列问题
200. 岛屿数量
1254. 统计封闭岛屿的数目
1020. 飞地的数量
695. 岛屿的最大面积
1905. 统计子岛屿
二、广度搜索
BFS代码框架
127. 单词接龙
111. 二叉树的最小深度
752. 打开转盘锁
773. 滑动谜题
bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false);DFS(0, rooms, visited);// 判断是否所有房间都被访问过了for (bool i : visited) {if (!i) return false;}return true;}// 采用深度优先搜索void DFS(int index, const vector<vector<int>>& rooms, vector<bool>& visited) {// 若已访问过，直接返回if (visited[index]) {return;}visited[index] = true;for (int key : rooms[index]) {DFS(key, rooms, visited);}}本题的本质是判断各个房间连成的有向图（来源：代码随想录），采用广度优先搜索(BFS) 还是 深度优先搜索(DFS) 都可以。
解决这类问题，和回溯法很类似，心中要有问题的抽象树结构。本题利用visited数组记录访问过的房间，最后判断是否所有元素都为true，即可判定能否遍历所有房间。
岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路。
vector<vector<int>> dirs = { {-1,0}, {1,0}, {0,-1}, {0,1} };vector<vector<bool>> visited;void dfs(vector<vector<char>>& grid, int i, int j, vector<vector<bool>> visited) {int m = grid.size();int n = grid[0].size();// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return;// 访问判断if (visited[i][j]) return;// 进入节点 (i, j)visited[i][j] = true;// 递归遍历上下左右的节点for (auto d : dirs) {int next_i = i + d[0];int next_j = j + d[1];dfs(grid, next_i, next_j, visited);}// 离开节点 (i, j)}class Solution {
public:int m;int n;int numIslands(vector<vector<char>>& grid) {m = grid.size();n = grid[0].size();int res = 0;// 遍历地图for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {// 发现陆地，岛屿数+1if (grid[i][j] == '1') res++;// 随之淹没这个岛屿dfs(grid, i, j);}}return res;}void dfs(vector<vector<char>>& grid, int i, int j) {// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return;// 递归返回条件：遇到水if (grid[i][j] == '0') return;// 若不是水，把该位置淹没成水grid[i][j] = '0';// 遍历周围区域，把周围的陆地全部淹没dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
};遇到岛屿，就用dfs淹没该岛屿上所有的陆地。判断是否是海水，即判断是否为'0'，也类似visited数组的作用。
class Solution {
public:int m;int n;int closedIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;for (int j = 0; j < n; j++) {// 把靠上边的岛屿淹掉dfs(grid, 0, j);// 把靠下边的岛屿淹掉dfs(grid, m - 1, j);}for (int i = 0; i < m; i++) {// 把靠左边的岛屿淹掉dfs(grid, i, 0);// 把靠右边的岛屿淹掉dfs(grid, i, n - 1);}// 遍历 grid，剩下的岛屿都是封闭岛屿for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {res++;dfs(grid, i, j);}}}return res;}void dfs(vector<vector<int>>& grid, int i, int j) {// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return;// 递归返回条件：遇到水if (grid[i][j] == 1) return;// 若不是水，把该位置淹没成水grid[i][j] = 1;// 遍历周围区域，把周围的陆地全部淹没dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
};本题与上一题的区别是：靠边的陆地不算作「封闭岛屿」。因此先利用dfs将靠边的陆地淹没，那么剩下的岛屿就都是封闭岛屿了。
class Solution {
public:int m;int n;int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;for (int j = 0; j < n; j++) {// 把靠上边的岛屿淹掉dfs(grid, 0, j);// 把靠下边的岛屿淹掉dfs(grid, m - 1, j);}for (int i = 0; i < m; i++) {// 把靠左边的岛屿淹掉dfs(grid, i, 0);// 把靠右边的岛屿淹掉dfs(grid, i, n - 1);}// 遍历 grid，剩下的岛屿都是封闭岛屿。统计封闭岛屿的面积即可。for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {res++;}}}return res;}void dfs(vector<vector<int>>& grid, int i, int j) {// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return;// 递归返回条件：遇到水if (grid[i][j] == 0) return;// 若不是水，把该位置淹没成水grid[i][j] = 0;// 遍历周围区域，把周围的陆地全部淹没dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
};本题和上一题类似，区别在于淹没掉所有非封闭岛屿后，遍历过程中不需要再淹没封闭岛屿。对封闭岛屿统计其面积即可。
class Solution {
public:int m;int n;int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {// 遇到陆地，则淹没这片岛屿，并利用dfs求解该岛屿的面积if (grid[i][j] == 1) {res = max(res, dfs(grid, i, j));}}}return res;}int dfs(vector<vector<int>>& grid, int i, int j) {// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return 0;// 递归返回条件：遇到水if (grid[i][j] == 0) return 0;// 若不是水，把该位置淹没成水grid[i][j] = 0;// 遍历周围区域，把周围的陆地全部淹没。+1是指统计当前所在(i,j)处的陆地面积return dfs(grid, i + 1, j) + dfs(grid, i, j + 1) +dfs(grid, i - 1, j) + dfs(grid, i, j - 1) + 1;}
};本题和前面的题不同，要统计岛屿的面积。岛屿的面积可以利用dfs的返回值获得，记录每次淹没的陆地的个数。
class Solution {
public:int m;int n;int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {m = grid1.size();n = grid1[0].size();int res = 0;// 把2中不可能是子岛屿的岛利用dfs淹没for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid1[i][j] == 0 && grid2[i][j] == 1) {// grid2中的这个岛屿肯定不是子岛，淹掉dfs(grid2, i, j);}}}// 统计2中剩下的岛屿数量for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid2[i][j] == 1) {res++;dfs(grid2, i, j);}}}return res;}void dfs(vector<vector<int>>& grid, int i, int j) {// 越界判断if (i < 0 || j < 0 || i >= m || j >= n) return;// 递归返回条件：遇到水if (grid[i][j] == 0) return;// 若不是水，把该位置淹没成水grid[i][j] = 0;// 遍历周围区域，把周围的陆地全部淹没。+1是指统计当前所在(i,j)处的陆地面积dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
}; 如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
借助该思想将不是子岛的岛屿利用dfs淹没后，再求解grid2剩余的岛屿数量即可。
拓展：本题也可以借助 Union Find 并查集算法 来判断。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {Queue<Node> q; // 核心数据结构Set<Node> visited; // 避免走回头路q.push(start); // 将起点加入队列visited.insert(start);int step = 0; // 记录扩散的步数while (q not empty) {int sz = q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i = 0; i < sz; i++) {Node cur = q.pop();/* 划重点：这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj()) {if (x not in visited) {q.push(x);visited.insert(x);}}}/* 划重点：更新步数在这里 */step++;}
}当问题可以被抽象成一幅图，每个节点有 k个相邻的节点，同时要求最短距离。那么就可以考虑使用BFS算法。
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {// 转化为set便于判断是否存在unordered_set<string> wordSet(wordList.begin(), d());// endWord不存在直接返回0if (wordSet.find(endWord) == d()) return 0;// 访问标记，同时记录了当前路径长度unordered_map<string, int> visited;// 采用广度搜索，最先返回的一定是最短路径queue<string> ladder;ladder.push(beginWord);visited.insert(make_pair(beginWord, 1));while (!pty()) {string word = ladder.front();int pLength = visited[word];ladder.pop();// 广度搜索：寻找单词的所有可能解for (int i = 0; i < word.size(); i++) {string nextWord = word;// 寻找满足要求的新单词for (int j = 0; j < 26; j++) {nextWord[i] = 'a' + j;// 找到了新单词且为最后一个if (nextWord == endWord) return pLength + 1;// 找到了符合要求的新单词，入队if (wordSet.find(nextWord) != d() && visited.find(nextWord) == d()) {visited.insert(make_pair(nextWord, pLength + 1));ladder.push(nextWord);}}}}return 0;}本题只需要求出最短长度就可以了，不用找出路径（来源：代码随想录）：
所以这道题要解决两个问题：
无向图需要标记位，标记着节点是否走过，否则就会死循环；同时可以利用set加快搜索速度。
【本题在“二叉树”章节中，采用了后序遍历的方式实现】
int minDepth(TreeNode* root) {if (!root) return 0;queue<TreeNode*> q;q.push(root);int res = 0;while (!q.empty()) {res++;int sz = q.size();for (int i = 0; i < sz; ++i) {TreeNode* cur = q.front();q.pop();if (!cur->left && !cur->right) return res;if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}}return res;}BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。
假设二叉树是满二叉树时，节点数为
N。对于 DFS 算法来说：空间复杂度无非是递归堆栈，最坏情况下是树的高度，也就是
O(logN)。但是对于BFS 算法：队列中每次都会储存着二叉树一层的节点，最坏情况下空间复杂度是树的最底层节点的数量
N/2，用 Big O 表示的话即O(N)。
class Solution {
public:int openLock(vector<string>& deadends, string target) {// deadends转化为set方便查找set<string> deadends_set(deadends.begin(), d());if (unt("0000") != 0) return -1;// 有可能出现走回头路的情况，如0000向上拨得到1000，之后1000向下拨又返回0000，需要去重set<string> visited;int res = 0;// BFS算法：将可能的八种选择抽象为与当前节点相邻的八个节点，求最短路径queue<string> q;q.push("0000");visited.insert("0000");while (!q.empty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {string cur = q.front();q.pop();if (cur == target) return res;for (int j = 0; j < 4; ++j) {string temp_up = plusOne(cur, j);if (unt(temp_up) == 0 && unt(temp_up) == 0) {q.push(temp_up);visited.insert(temp_up);}string temp_down = minusOne(cur, j);if (unt(temp_down) == 0 && unt(temp_down) == 0) {q.push(temp_down);visited.insert(temp_down);}}}res++;}// 可选结果为空仍没找到结果，说明无解return -1;}// 将 s[j] 向上拨动一次string plusOne(string s, int j) {if (s[j] == '9')s[j] = '0';elses[j] += 1;return s;}// 将 s[i] 向下拨动一次string minusOne(string s, int j) {if (s[j] == '0')s[j] = '9';elses[j] -= 1;return s;}
};本题需要注意走回头路的情况。比如从 "0000" 拨到 "1000"，但是之后从队列拿出 "1000" 时，还会拨出一个 "0000"，这样会产生死循环。因此要利用visited数组进行去重。
BFS 算法的优化思路：双向 BFS——从起点和终点同时开始扩散，当两边有交集的时候停止。【要求必须知道终点位置，比如752.打开转盘锁问题是已知终点位置的】
- 不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。
- while 循环的最后交换
q1和q2的内容，所以只要默认扩散q1就相当于轮流扩散q1和q2- 每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些
- 参考连接：BFS 算法解题套路框架 :: labuladong的算法小抄
int slidingPuzzle(vector<vector<int>>& board) {// 将二维数组压缩为一维数组string target = "123450";string s = "";for (int i = 0; i < 2; ++i) {for (int j = 0; j < 3; ++j) {s.push_back('0' + board[i][j]);}}// 定义一维数组元素在原二维数组位置的相邻位置vector<vector<int>> neighbors = {{1, 3},{0, 4, 2},{1, 5},{0, 4},{3, 1, 5},{4, 2}};// BFS算法int res = 0;set<string> visited;queue<string> q;q.push(s);visited.insert(s);while (!q.empty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {string cur_s = q.front();q.pop();if (cur_s == target) return res;// 进行一次交换int zero_idx = cur_s.find('0');for (auto ex_idx : neighbors[zero_idx]) {string next_s = cur_s;swap(next_s[zero_idx], next_s[ex_idx]);if (unt(next_s) != 1) {q.push(next_s);visited.insert(next_s);}}}res++;}return -1;}本题在于选择恰当的表征方式，把board转化为数的一个结点（采用一维字符串的形式），然后利用BFS进行搜索。
int minimumMoves(vector<vector<int>>& grid) {int n = grid.size();// 存储每个单元格蛇身1/0时的距离vector<vector<array<int, 2>>> dist(n, vector<array<int, 2>>(n, { -1, -1 }));dist[0][0][0] = 0;// 三元组 (x,y,dir) 表示蛇尾位置和蛇身方向queue<tuple<int, int, int>> q;q.push(make_tuple(0, 0, 0));while (!q.empty()) { int x, y, dir;tie(x, y, dir) = q.front();q.pop();if (dir == 0) {// 向右移动一个单元格if (y + 2 < n && dist[x][y + 1][0] == -1 && grid[x][y + 2] == 0) {dist[x][y + 1][0] = dist[x][y][0] + place(x, y + 1, 0);}// 向下移动一个单元格if (x + 1 < n && dist[x + 1][y][0] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) {dist[x + 1][y][0] = dist[x][y][0] + place(x + 1, y, 0);}// 顺时针旋转 90 度if (x + 1 < n && y + 1 < n && dist[x][y][1] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) {dist[x][y][1] = dist[x][y][0] + place(x, y, 1);}}else {// 向右移动一个单元格if (y + 1 < n && dist[x][y + 1][1] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) {dist[x][y + 1][1] = dist[x][y][1] + place(x, y + 1, 1);}// 向下移动一个单元格if (x + 2 < n && dist[x + 1][y][1] == -1 && grid[x + 2][y] == 0) {dist[x + 1][y][1] = dist[x][y][1] + place(x + 1, y, 1);}// 逆时针旋转 90 度if (x + 1 < n && y + 1 < n && dist[x][y][0] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) {dist[x][y][0] = dist[x][y][1] + place(x, y, 0);}}}return dist[n - 1][n - 2][0];}广度优先搜索方法的正确性在于：我们一定不会到达同一个位置两次及以上，因为这样必定不是最少的移动次数。
本题用蛇尾坐标表示蛇的所在位置，利于旋转坐标变换。
本文发布于:2024-02-02 13:05:28，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170685032743993.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
