目录

1、单词搜索

2、岛屿数量

2.1 DFS

2.2 BFS

3、腐烂的橘子

---

1、单词搜索

单词搜索_牛客题霸_牛客网 (nowcoder.com)

这道题我们就是先遍历数组board，若遇到了与word[0]相等的字符，则以这个字符为起点进行搜索，搜索可以是dfs，也可以是bfs，在这里我们使用的是dfs。

class Solution {public:int m, n;bool vis[101][101] = {0}; // vis用来标记某一位置是否已经被搜索过了，0表示没有，1表示有int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool dfs(vector<string>& board, int i, int j, string& word, int pos){if(pos == word.size() - 1) return true;vis[i][j] = true;for(int k = 0;k < 4;k++){int a = i + dx[k], b = j + dy[k];if(a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && board[a][b] == word[pos + 1]){if(dfs(board, a, b, word, pos + 1)) return true;}}vis[i][j] = false; // 恢复现场return false;}bool exist(vector<string>& board, string word) {m = board.size(), n = board[0].size();for(int i = 0;i < m;i++)for(int j = 0;j < n;j++)if(board[i][j] == word[0])if(dfs(board, i, j, word, 0)) return true;return false;}};

2、岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

2.1 DFS

我们需要先遍历二维数组，当遇到字符1时，就将ans++，并将1所在的整个岛屿都变成0，都变成0后就继续刚刚的遍历二维数组，重复上面的操作，直到将二维数组遍历完，ans就是岛屿数量。

遇到1时，将整个岛屿变成0的操作，就可以使用DFS。从遇到1的地点开始，进行DFS，直到将整个岛屿都变成了0结束

class Solution {
private://  DFSint n, m;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};void dfs(vector<vector<char>>& grid, int x, int y){// 若位置不合法或者是'0'，就返回if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0') return ;grid[x][y] = '0'; // 将当前位置变成'0'for(int i = 0;i < 4;i ++) // 搜索当前位置的上下左右4个位置dfs(grid, x + dx[i], y + dy[i]);}
public:int numIslands(vector<vector<char>>& grid) {n = grid.size(), m = grid[0].size();int sum = 0;for(int i = 0;i < n;i ++)for(int j = 0;j < m;j ++)if(grid[i][j] == '1'){sum ++;dfs(grid, i, j);}return sum;}
};

2.2 BFS

与DFS前面步骤是类似的。我们需要先遍历二维数组，当遇到字符1时，就将ans++，并将1所在的整个岛屿都变成0，都变成0后就继续刚刚的遍历二维数组，重复上面的操作，直到将二维数组遍历完，ans就是岛屿数量。

遇到1时，将整个岛屿变成0的操作，就可以使用BFS。从遇到1的地点开始，进行DFS，直到将整个岛屿都变成了0结束

class Solution {
private:// BFSint n, m;const int dx[4] = {-1, 1, 0, 0};const int dy[4] = {0, 0, -1, 1};void bfs(vector<vector<char>>& grid, int x, int y){queue<pair<int, int>> q;q.push({x, y});while(!q.empty()){int currentRow = q.front().first, currentCol = q.front().second;q.pop();grid[currentRow][currentCol] = '0';  // 标记为已访问for(int k = 0; k < 4; k++){int i = currentRow + dx[k], j = currentCol + dy[k];if(i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == '1') q.push({i, j});}}}public:int numIslands(vector<vector<char>>& grid) {if (grid.empty() || grid[0].empty()) return 0;  // 检查边界条件n = grid.size(), m = grid[0].size();int sum = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(grid[i][j] == '1'){sum++;bfs(grid, i, j);}return sum;}
};

此时就会发现逻辑全对，但是却超时了。这是因为我们在从队列中取出一个点时才标记已访问，这样会导致重复加入，应该在放入队列时就标记已访问。

若取出时才标记已访问，会发现下标为[1][1]的点会被下标为[0][1]、[1][0]的点都放入一次队列。

class Solution {
private:// BFSint n, m;const int dx[4] = {-1, 1, 0, 0};const int dy[4] = {0, 0, -1, 1};void bfs(vector<vector<char>>& grid, int x, int y){queue<pair<int, int>> q;q.push({x, y});grid[x][y] = '0'; // 放入时就标记while(!q.empty()){int currentRow = q.front().first, currentCol = q.front().second;q.pop();for(int k = 0; k < 4; k++){int i = currentRow + dx[k], j = currentCol + dy[k];if(i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == '1'){q.push({i, j});grid[i][j] = '0';}}}}public:int numIslands(vector<vector<char>>& grid) {if (grid.empty() || grid[0].empty()) return 0;  // 检查边界条件n = grid.size(), m = grid[0].size();int sum = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(grid[i][j] == '1'){sum++;bfs(grid, i, j);}return sum;}
};

3、腐烂的橘子

994. 腐烂的橘子 - 力扣（LeetCode）

这道题看似与岛屿数量是有点类似的。我们可以先遍历二维数组，当遇到值为2的结点时，就以此结点为起点，进行搜索。注意：这道题的搜索就好使用BFS，因为橘子腐烂的传递是向四个方向进行传递的。这样子的思路是会有问题的，因为一个区域内可能不止有一个腐烂的橘子，这些橘子是会一起向四周扩散的。所以，使用多源BFS。

正确的做法是：我们先遍历原数组，值为2的结点都放入队列，我们一次处理队列中的所有元素

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size(), sum = 0;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};queue<pair<int, int>> q;for(int i = 0;i < n;i ++)for(int j = 0;j < m;j ++)if(grid[i][j] == 2) q.push({i, j});while(!q.empty()){vector<pair<int, int>> v;while(!q.empty()){v.push_back({q.front().first, q.front().second});q.pop();}// 标记最后一步是否有执行,因为当全扩散完后，还会再循环一次，导致sum多加一次，所以有一个标记，当没有向队列中放入时，sum就不会++bool flag = false; for(int k = 0;k < v.size();k++){for(int i = 0; i < 4; i++){int a = v[k].first + dx[i], b = v[k].second + dy[i];if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1){q.push({a, b});grid[a][b] = 2;flag = true;}}}if(flag) sum ++;}for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(grid[i][j] == 1) return -1; // 若还有1，表示有些位置一定不会腐烂return sum;}
};